Searching a string

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

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?

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.

Quote:

Original post by Scet 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?

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 Scet 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.

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.

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