Sherlock and Anagrams

                            Solution in C :

In C :


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef struct node{
    int s;
    int e;
}node;

void combine(node *A,int start,int end,int index,int *sum,node *temp,char *str){
    
    if(index == 2){
        int m[26] = {0};
        int i;
        for(i=temp[0].s;i<=temp[0].e;i++)
            m[str[i] - 'a']++;
        
        for(i=temp[1].s;i<=temp[1].e;i++)
            m[str[i] - 'a']--;
        
        for(i=0;i<26;i++)
            if(m[i])
                return;
            
        *sum += 1;
        return;
    }
    
    int i;
    
    for(i=start;i<end;i++){
        temp[index] = A[i];
        combine(A,i+1,end,index+1,sum,temp,str);
    }
    
}

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int t;
    scanf("%d",&t);
    
    while(t--){
        char *str = (char*)malloc(sizeof(char)*101);
        scanf("%s",str);
        
        node *A = (node*)malloc(sizeof(node)*100);
        
        int index = 0;
        
        int i;
        int len = strlen(str);
        
        int count;
        int sum = 0;
        
        while(index<len){
            count = 0;
            for(i=0;i<len;i++){
                A[i].s = i;
                if(i+index>=len)
                    break;
                A[i].e = i+index;
                count++;
            }
            
            if(count>=2){
                node *temp = (node*)malloc(sizeof(node)*2);
                combine(A,0,count,0,&sum,temp,str);
            }
            index++;
        }
        
        printf("%d\n",sum);
        
    }
    return 0;
}
                        

                        Solution in C++ :

In C ++ :

#include<bits/stdc++.h>
#include <cstdio>
#define MAX 5000
using namespace std;
map<string,int> mp ;
int main(){
	ios::sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--){
		mp.clear();
		string s,sn,ss ;
		int j;
		cin>>s;
		int l=s.length();
		for(int k=0;k<l;k++){
			ss = "";
			for(int i=0;i<l-k;i++){	
					j = k+i;
					ss = ss + s[j];
					sn = ss ;
					sort(sn.begin() , sn.end());
					mp[sn]++;
			}
		}
		long long int ans = 0 ;
		map<string,int> :: iterator it ;
		for(it = mp.begin() ; it != mp.end() ; it++){
			long long  vl = (long long)(it->second) ;
			if(vl > 1){				
				ans += (vl*(vl-1))/2LL ;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}
                    

                        Solution in Java :

In Java :


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
    private static int count[][] = new int[128][110];

    private static void resetCount() {
        for (int i = 0; i < count.length; i++) for (int j = 0; j < count[i].length; j++) count[i][j] = 0;
    }
    
    private static boolean areAnagrams(int from1, int to1, int from2, int to2) {
        for (int i = 'a'; i <= 'z'; i++) {
            if (count[i][to1+1]-count[i][from1] != count[i][to2+1]-count[i][from2])
                return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        final int TC = Integer.parseInt(sc.nextLine());
        for (int tc = 0; tc < TC; tc++) {
            final char s[] = sc.nextLine().toCharArray();
            resetCount();
            count[s[0]][1] = 1;
            for (int i = 1; i < s.length; i++) {
                for (int j = 'a'; j <= 'z'; j++) count[j][i+1] = count[j][i];
                count[s[i]][i+1]++;
            }
            int res = 0;
            for (int len = 1; len <= s.length-1; len++) {
                for (int from = 0; from <= s.length-len; from++) {
                    for (int to = from+1; to <= s.length-len; to++) {
                        if (areAnagrams(from, from+len-1, to, to+len-1)) res++;
                    }
                }
            }
            System.out.println(res);
        }
    }
}
                    

                        Solution in Python : 
                            
In Python3 :


for _ in range(int(input())):
    was = dict()
    s = input()

    n = len(s)
    for i in range(n):
        for j in range(i, n):
            cur = s[i:j + 1]
            cur = ''.join(sorted(cur))
            was[cur] = was.get(cur, 0) + 1

    ans = 0
    for x in was:
        v = was[x]
        ans += (v * (v - 1)) // 2

    print(ans)