Hacker Rank “Sherlock and Anagrams”

 

Given a string , find the number of “unordered anagrammatic pairs” of substrings.

Input Format
First line contains , the number of testcases. Each testcase consists of string in one line.

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

Sample Input#00

2
abba
abcd

Sample Output#00

4
0

Sample Input#01

5
ifailuhkqq
hucpoltgty
ovarjsnrbf
pvmupwjjjf
iwwhrlkpek

Sample Output#01

3
2
2
6
3

Explanation: 

abba

a|0,0| a|3,3|

b|1,1| b|2,2|

ab|0,1| ab|2,3|

abb|0,2| abb|1,3|

4

---

abcd

0

---

ifailuhkqq

i|0,0| i|3,3|

q|8,8| q|9,9|

afi|0,2| afi|1,3|

3

---

hucpoltgty

t|6,6| t|8,8|

gt|6,7| gt|7,8|

2

---

ovarjsnrbf

r|3,3| r|7,7|

jnrs|3,6| jnrs|4,7|

2

---

pvmupwjjjf

p|0,0| p|4,4|

j|6,6| j|7,7|

j|6,6| j|8,8|

j|7,7| j|8,8|

jj|6,7| jj|7,8|

mpuv|0,3| mpuv|1,4|

6

---

iwwhrlkpek

w|1,1| w|2,2|

k|6,6| k|9,9|

ekp|6,8| ekp|7,9|

3

---

Solution using c++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool check(string str1, string str2);
int main()
{
  int numOfCases;
  int counter = 0;
  
  cin >> numOfCases;
  for (int i = 0; i < numOfCases; i++)
  {
     string temp;
     cin >> temp;
     int length = temp.length(); 
     
     for (int subLength = 1; subLength < length; subLength++)
     {
       vector <string> subStrings;
       for (int n = 0; n < length - subLength + 1; n++)
           subStrings.push_back(temp.substr(n, subLength));
       
       for (int i= 0; i< subStrings.size()-1; i++)
       {
          for (int j= i+ 1; j< subStrings.size(); j++)
          {
              if (check(subStrings[i], subStrings[j]))
                  counter++;
          }
       }
    }
   cout << counter << endl;
   counter = 0;
  }
 return 0;
}
bool check(string str1, string str2)
{
   bool flag = true;
   if (str1.length() != str2.length())
       return false;
   else
   {
     string sortedStr1 = str1;
     sort(sortedStr1.begin(), sortedStr1.end());

     string sortedStr2 = str2;
     sort(sortedStr2.begin(), sortedStr2.end());

     for (int i = 0; i < str1.length(); i++)
     {
       if (sortedStr1[i] != sortedStr2[i])
           flag = false;
      }
      return flag;
   }
}

Advertisements