Count of total anagram substrings

Count of total anagram substrings

Given a string of lower alphabet characters, count total substring of this string which are anagramto each other.

The idea is to create a map. We use character frequencies as keys and corresponding counts as values. We can solve this problem by iterating over all substrings and counting frequencies of characters in every substring. We can update frequencies of characters while looping over substrings i.e. there won’t be an extra loop for counting frequency of characters.
In below code, a map of key ‘vector type’ and value ‘int type’ is taken for storing occurrence of ‘frequency array of length 26’ of substring characters. Once occurrence ‘o’ of each frequency array is stored, total anagrams will be the sum of o*(o-1)/2 for all different frequency arrays because if a particular substring has ‘o’ anagrams in string total o*(o-1)/2 anagram pairs can be formed.

int countOfAnagramSubstring(string str)

{

    int N = str.length();

 

    // To store counts of substrings with given

    // set of frequencies.

    map<vector<int>, int> mp;

 

    // loop for starting index of substring

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

    {

        vector<int> freq(MAX_CHAR, 0);

 

        // loop for length of substring

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

        {

            // update freq array of current

            // substring

            freq[toNum(str[j])]++;

 

            // increase count corresponding

            // to this freq array

            mp[freq]++;

        }

    }

 

    // loop over all different freq array and

    // aggregate substring count

    int result = 0;

    for (auto it=mp.begin(); it!=mp.end(); it++)

    {

        int freq = it->second;

        result += ((freq) * (freq-1))/2;

    }

    return result;

}

Count of total anagram substrings