Sherlock and Anagrams : Challenge | Strings | Algorithms | HackerRank
Given a string S, find the number of unordered anagramic pairs of substrings.
For S={S[1,1],S[4,4]} , {S[1,2],S[3,4]} , {S[2,2],S[3,3]} and {S[1,3],S[2,4]} .
cin >> s;
int len = (int)s.size();
for (int i = 0; i < len; i++)
{
for (int l = 1; i + l - 1 < len; l++)
{
string t = s.substr(i, l);
sort(t.begin(), t.end());
m[t]++;
}
}
long long ans = 0;
for (map<string, int>::iterator it = m.begin(); it != m.end(); ++it)
ans += (long long)(it->second) * (it->second - 1) / 2;
cout << ans << endl;
http://www.cnblogs.com/tonix/p/4468668.html
-- no need to sort
Read full article from Sherlock and Anagrams : Challenge | Strings | Algorithms | HackerRank
Given a string S, find the number of unordered anagramic pairs of substrings.
For S=
abba, anagramic pairs are:
How to check anagrams
We need to check if stringS1 and S2 are anagrams, we first build frequency table where frequency[i] stores the frequency of character i+
We need to check if string
a. If two strings have same frequency table they are anagrams.
Approach 1
Traverse over allO(N×N) substrings and for each substring in O(N) build the frequency table and store after hashing. For each key in hashtable, we add value×(value−1)2 pairs to answer. A factor of 26 arrives in complexity due to hashing of frequency tables. Overall complexity: O(N3×26)
Traverse over all
Approach 2
Starting fori=1 to N , we dynamically build frequency for substring S[i,j] where j ranges from i to N . So, overall complexity here would be O(N2×26) .
https://github.com/derekhh/HackerRank/blob/master/sherlock-and-anagrams.cppStarting for
cin >> s;
int len = (int)s.size();
for (int i = 0; i < len; i++)
{
for (int l = 1; i + l - 1 < len; l++)
{
string t = s.substr(i, l);
sort(t.begin(), t.end());
m[t]++;
}
}
long long ans = 0;
for (map<string, int>::iterator it = m.begin(); it != m.end(); ++it)
ans += (long long)(it->second) * (it->second - 1) / 2;
cout << ans << endl;
http://www.cnblogs.com/tonix/p/4468668.html
-- no need to sort
Read full article from Sherlock and Anagrams : Challenge | Strings | Algorithms | HackerRank
