I've been challenging myself to look at algorithms and try to change them in ordem to make them the fastest i can. Recently i tried an algorithm which searches for the longest sequence of any letter on a string. The naive answer looks at all letters and when the current sequence is bigger than the biggest sequence found, the new biggest become the current. Example:
With C for current sequence and M for maximum sequence, order of letters checked and variables updates goes like this: AAAACCDDD-> A(C=1,M=1)->A(C=2,M=2)->A(C=3,M=3)->A(C=4,M=4)->C(C=1,M=4)->C(C=2,M=4)->D(C=1,M=4)->D(C=2,M=4)->D(C=3,M=4) Answer: 4 It can be faster by stopping when there is no way to get a new biggest sequence given M,the place you are in the string and the string size.
I've tried and came up with an algorithm which usually accesses less elements of the string, I think will be easier to explain like this:
Instead of jumping 1 by 1, you jump what would be necessary to have a new biggest sequence if all letters across the jump were the same. So for example after you read AAAB, you would jump 3 spots because you suppose all 3 next letters are B (AAABBBB). Of course they might not be, and that is why you now go backwards counting consecutive B's right behind your position. Your next "jump" will be lower depending on how many B's you've found. So for instance
AAABCBBBBD after the jump you are in the third B. You go backwards and find one B, backwards again and finding a C you stop. Now you already know you have a sequence of 2 so your next jump can't be of 3 -you might miss a sequence of 4 B's. So you jump 2 and get to a B. Go backwards one and find a B. The next backwards position is where you started so you know that you found a sequence of 4. In that example it didnt have much of a difference but if you use instead a string like AAABBBBCDDECEE you can see that after you jumped from the first C to the last C you would only need to backtrack once because after seeing that the letter behind you is E you don't care anymore about what was across that jump.
I've coded both methods and that second one has been 2 to 3 times faster. Now I'm really curious to know, is there a faster way to find it?