If you need to search for characters in this very same string more than once, then a possible approach is to divide the string into smaller parts, possibly recursively, and to use bloom filters for each of these parts.
Since a bloom filter can tell you for sure if an character is not in the part of the string that's "represented" by the filter, you can skip some parts while searching for characters.