As I was reading this (Find the most common entry in an array), the Boyer and Moore's Linear Time Voting Algorithm was suggested.
If you follow the link to the site, there is a step by step explanation of how the algorithm works. For the given sequence, AAACCBBCCCBCC
it presents the right solution.
When we move the pointer forward over an element e:
- If the counter is 0, we set the current candidate to e and we set the counter to 1.
- If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.
If I use this algorithm on a piece of paper with AAACCBB
as input, the suggested candidate would become B what is obviously wrong.
As I see it, there are two possibilities
AAACCBBCCCBCC
, are completely incompetent and should be fired on the spot (doubtfull).Note: Here is a a C++ implementation of the algorithm from Niek Sanders. I believe he correctly implemented the idea and as such it has the same problem (or doesn't it?).
The algorithm only works when the set has a majority -- more than half of the elements being the same. AAACCBB
in your example has no such majority. The most frequent letter occurs 3 times, the string length is 7.