Sherlock and Anagrams Optimization

Question

From Hackerrank:

Given a string S, find the number of "unordered anagrammatic pairs" of substrings. In other words, find the number of unordered pairs of substrings of S that are anagrams of each other.

Two strings are anagrams of each other if the letters of one string can be rearranged to form the other string.

Input Format

First line contains T, the number of testcases. Each testcase consists of string S in one line.

Constraints

1 <= t <= 10

2 <= length(s) <= 100

String S contains only the lowercase letters of the English alphabet.

Output Format

For each testcase, print the required answer in one line.

I am losing two test cases with Time Limit Exceeded. Can somebody please tell me how to optimize the code?

#include <bits/stdc++.h>

using namespace std;

int sherlockAndAnagrams(string s)
{ 

    unordered_map<char,int> count1,count2;
    unordered_map<char,int>::iterator it;
    int l=s.length();
    int len1,len2;
    int wall1,wall2;
    int cnt=0;
    int flg=0;
    int i,j;
    int dflg;
    wall1=0,wall2=l-1;
    for(wall1=0;wall1<l-1;++wall1)
    {
        len1=1;
        count1.clear();
        for(i=wall1;i<l-1;++i,++len1)
        {
            ++count1[s[i]];
            for(wall2=l-1;wall2>wall1;--wall2)
            {
                len2=1;
                count2.clear();
                flg=0;
                dflg=0;
                for(j=wall2;j>wall1;--j,++len2)
                {
                    ++count2[s[j]];
                    if(len2>len1)
                        break;
                    if(len2==len1)
                    {
                        dflg=1;
                        for(it=count1.begin();it!=count1.end();++it)
                        {
                            if(it->second!=count2[it->first])
                            {
                                flg=1;
                                break;
                            }
                        }
                        break;
                    }
                }
                if(dflg==1 && flg==0)
                        ++cnt;
            }
        }
    }
    return cnt;
}





int main() {
        int q;
        cin >> q;
        for(int a0 = 0; a0 < q; a0++){
            string s;
            cin >> s;
            int result = sherlockAndAnagrams(s);
            cout << result << endl;
        }
        return 0;
    }

Answer 1

Your problem is not in the code, but in your algorithm. Brute-forcing the solution as you are doing is fundamentally slow, and you need to tackle the problem from a different angle if you want to make a substantial dent in your runtime.

The problem is constrained in two specific ways we can exploit:

1. Only letters in the 'a'->'z' range are admissible. That's only 26 letters.
2. Only strings of length <= 100 characters are admissible. By extension, this means we'll never have more than 100 substrings of a given length to deal with.

Now, if I had a function that converts a substring into "some" representation that's common between annagrammic pairs, but only between annagrammic pairs, I could simply generate that representation for each substring and work off that datastructure instead (probably by using it as a key to a map of number of instances seen).

Since we only have 26 possible letters, a simple std::array<uint8_t, 26>, where each cell represents the number of times a given letter appears in the substring, has all the properties we need.

Just to make sure I'm not spouting nonsense, I gave it a try, and my solution using these principles solves all the hackerrank test cases in under 10ms.

I encourage you to give it a try by yourself, but if you request it, I'll be glad to post the code for my solution here.