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.

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 ++;
   }
}

The previous awser don't covert the fact that the caracter in the middle (the separator) must be different.

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.

Must this characters be different ? Here what I though if it's have to be different...

    int trueNbPair =0;
    for (int i=1;i<str.length()-1;i++)
    {
        char prev = str.charAt(i-1);
        char current = str.charAt(i);
        char next = str.charAt(i+1);

        if (prev == next && current!= prev)
        {
            trueNbPair++;
        }
    }

with recursion:

public int countPairs(String str)
{
    if(str.length() < 3)
        return 0;
    if(str.charAt(0) == str.charAt(2) && str.charAt(0) != str.charAt(1))
        return 1 + countPairs(str.substring(1));
    return countPairs(str.substring(1));
}