How can I count the number of occurrences of a simple pattern in a string?

For this question, a “pair” in a string is defined as a situation where two instances of one character are separated by another character. So in “AxA” the A’s make a pair. Pairs can overlap, so “AxAxA” contains three pairs; two for A and one for x.

Further examples:

countPairs(“axa”) → 1
countPairs(“axax”) → 2
countPairs(“axbx”) → 1

I was asked how to compute the number of pairs in a given string in an interview yesterday, and I’m not sure how to do it.

Answer

An O(n) solution would be to iterate the string (from 0 to length-2) and (using charAt(..)) to verify whether the current character is equal to the current+2. If so, increment a pairsCount variable

int pairsCount = 0;
for (int i = 0; i < str.length() - 2; i ++) {
   if (str.charAt(i) == str.charAt(i + 2)) {
      pairsCount ++;
   }
}