# Searching a string

This topic is 4085 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hey, Given a string only consisting of a's and b's perhaps, which way to determind whether the string contains a equal amount og a's and b's is the fastet? I know that iterating through the whole string counting both entries on the way is a possibility, but it just seems so stupid to me. Anyone's up for a go?

##### Share on other sites
You have to read every character at least once to determine this, and the naive algorithm only reads every character once already.

##### Share on other sites
Set a signed integer variable to 0. Iterate over the string and for each character if the character is 'a' increment the variable, if it's 'b' decrement the variable.

If the variable is 0 at the end of the loop there are an equal number of 'a' and 'b' characters.

And no, there's really no way to avoid iterating over the string. How do you expect to tell if there are an equal number without reading each character at least once?

##### Share on other sites
If you only have two possible characters then isn't it impossible for a string with an odd length to contain an equal number of the characters? Also if you are counting one at a time and one count is higher then the strings length divided by 2 plus 1, you already know the answer. This could help to "early-out" and avoid having to go through each one.

##### Share on other sites
Quote:
 Original post by ScetIf you only have two possible characters then isn't it impossible for a string with an odd length to contain an equal number of the characters?

Good point. If this is a C-string however you'd still have to iterate over it to find the length, which would defeat this method because then you'd have to go over it again after finding the length if the length turns out to be even.

Quote:
 Original post by ScetAlso if you are counting one at a time and one count is higher then the strings length divided by 2 plus 1, you already know the answer. This could help to "early-out" and avoid having to go through each one.

If this thing really has to be optimized (which I doubt) then I would say that this approach could potentially be slower if that isn't often the case due to the extra comparison. It would also be slower on C-strings because you'd have to iterate twice to find the length and then go over each character... same as above.

##### Share on other sites
If you really need to optimize you could cast the char * string to a int32 * (or even int64 * on 64-bit platforms), and access the string 4 bytes at a time. Some handy bit-shifting (and perhaps a lookup table) would allow you to count a's vs b's pretty quickly.

Almost certainly not worth the trouble, however.

Geoff

• 9
• 9
• 13
• 41
• 15