Given a string of lower alphabet characters, count total substring of this string which are anagram to each other.
Examples:
Input : str = “xyyx”
Output : 4
Total substrings of this string which
are anagram to each other are 4 which
can be enumerated as,
{“x”, “x”}, {"y", "y"}, {“xy”, “yx”},
{“xyy”, “yyx”}
Input : str = "geeg"
Output : 4
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. Below is the implementation of above idea.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
#define MAX_CHAR 26
int toNum(char c)
{
return (c - 'a');
}
int countOfAnagramSubstring(string str)
{
int N = str.length();
map<vector<int>, int> mp;
for (int i=0; i<N; i++)
{
vector<int> freq(MAX_CHAR, 0);
for (int j=i; j<N; j++)
{
freq[toNum(str[j])]++;
mp[freq]++;
}
}
int result = 0;
for (auto it=mp.begin(); it!=mp.end(); it++)
{
int freq = it->second;
result += ((freq) * (freq-1))/2;
}
return result;
}
int main()
{
string str = "xyyx";
cout << countOfAnagramSubstring(str) << endl;
return 0;
}
|
Java
import java.util.Arrays;
import java.util.HashMap;
public class anagramPairCount {
public static void main(String[] args) {
subString("kkkk");
}
static void subString(String s){
HashMap<String, Integer> map= new HashMap<>();
for(int i = 0; i < s.length(); i++){
for(int j = i; j < s.length(); j++){
char[] valC = s.substring(i, j+1).toCharArray();
Arrays.sort(valC);
String val = new String(valC);
if (map.containsKey(val))
map.put(val, map.get(val)+1);
else
map.put(val, 1);
}
}
int anagramPairCount = 0;
for(String key: map.keySet()){
int n = map.get(key);
anagramPairCount += (n * (n-1))/2;
}
System.out.println(anagramPairCount);
}
}
|
Python3
def countOfAnagramSubstring(s):
n = len(s)
mp = dict()
for i in range(n):
sb = ''
for j in range(i, n):
sb = ''.join(sorted(sb + s[j]))
mp[sb] = mp.get(sb, 0)
mp[sb] += 1
anas = 0
for k, v in mp.items():
anas += (v*(v-1))//2
return anas
s = "xyyx"
print(countOfAnagramSubstring(s))
|
C#
using System;
using System.Collections.Generic;
public class anagramPairCount {
public static void Main() {
subString("kkkk");
}
static void subString(String s){
Dictionary<string, int> map= new Dictionary<string, int>();
for(int i = 0; i < s.Length; i++){
for(int j = i; j < s.Length; j++){
char[] valC = s.Substring(i, j+1-i).ToCharArray();
Array.Sort(valC);
string val = new string(valC);
if (map.ContainsKey(val))
map[val]=map[val]+1;
else
map.Add(val, 1);
}
}
int anagramPairCount = 0;
foreach(string key in map.Keys){
int n = map[key];
anagramPairCount += (n * (n-1))/2;
}
Console.Write(anagramPairCount);
}
}
|
Javascript
<script>
function countOfAnagramSubstring(s){
let n = s.length
let mp = new Map()
for(let i=0;i<n;i++){
let sb = ''
for(let j=i;j<n;j++){
sb = (sb + s[j]).split('').sort().join('')
if(mp.has(sb))
mp.set(sb ,mp.get(sb)+1)
else mp.set(sb, 1)
}
}
let anas = 0
for(let [k, v] of mp){
anas += Math.floor((v*(v-1))/2)
}
return anas
}
let s = "xyyx"
document.write(countOfAnagramSubstring(s),"</br>")
</script>
|
Time complexity : O(N2logN)
Auxiliary Space : O(N)
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!