/*To approach this problem, its crucial to understand how to fetch all palindromes from a string
as it is a variation of that problem*/

long substrCount(int n, string s) {

    /*Conditons for palindrome:
    A.- All of the characters are the same, e.g. aaa.
    B.- All characters except the middle one are the same, e.g. aadaa.
    */
    long palCount = 0; 

    /*Two "pointers" in order to slide left and right to find palindrome*/
    int rPos = 0, lPos = 0;

    //Main loop that will traverse string
    for (int i = 0; i < n; i++)
    {
        //We set both "pointers" to i
        rPos = lPos = i;
        char letter = s[i];

        /*If where we are pointing, is within the interval of string and "pointers" value are the same
        that means that we found a palindrome, however, we must check if palindrome fullfill conditons A and B */
        while ((rPos < n) && (lPos >= 0) && (s[rPos] == s[lPos]))
        {

            //Check if all letters are the same, or first letter
            if (s[rPos] == letter)
            {
                palCount++;
                rPos++;
                lPos--;
            }
            else
            {
                /*If letters differ, then we have to check if we already moved our "pointers" from the
                starting position "i"*/
                if (rPos - i <= 1)
                {
                    /*This means we have not done that, so this means that we are in the first iteration of i
                    we increase the count and set the new letter to upper and lower limit of our first palindrome of
                    lenght > 1*/
                    palCount++;

                    /*As you can see here, a new letter is set, this means that for all of the next iterations,
                    all letters must match new letter*/
                    letter = s[rPos];
                    rPos++;
                    lPos--;
                }  
                else
                {
                    /*No match, so we break and "i" is incremented*/
                    break;
                }
            }
            
        }

        //Same process but for substrings of pair size
        rPos = i + 1;
        lPos = i;
        letter = s[i];

        /*If we have abba string, we will start evaluating substr(0,2) -> "ab",
        in this case, this while loop has a slight modification than the previous one, 
        here, we just have to make sure that all of the letters are the same*/
        while ((rPos < n) && (lPos >= 0) && (s[rPos] == s[lPos]) && (s[rPos] == letter))
        {
            palCount++;
            rPos++;
            lPos--;
        }

    }

    return palCount;

}