Count substrings with same first and last characters - GeeksforGeeks

Count substrings with same first and last characters - GeeksforGeeks
We are given a string S, we need to find count of all contiguous substrings starting and ending with same character.
f we carefully observe then we can realize that the answer just depends on frequencies of characters in the original string. For example in string abcab, frequency of ‘a’ is 2 and substrings contributing to answer are a, abca and a respectively, a total of 3, which is calculated by (frequency of ‘a’+1)C2.

int countSubstringWithEqualEnds(string s)

{

    int result = 0;

    int n = s.length();

 

    // Calculating frequency of each character

    // in the string.

    int count[MAX_CHAR] = {0};

    for (int i=0; i<n; i++)

        count[s[i]-'a']++;

 

    // Computing result using counts

    for (int i=0; i<MAX_CHAR; i++)

        result += (count[i]*(count[i]+1)/2);

 

    return result;

}

int countSubstringWithEqualEnds(string s)

{

    int result = 0;

    int n = s.length();

 

    // Iterating through all substrings in

    // way so that we can find first and last

    // character easily

    for (int i=0; i<n; i++)

        for (int j=i; j<n; j++)

            if (s[i] == s[j])

                result++;

 

    return result;

}

Read full article from Count substrings with same first and last characters - GeeksforGeeks