Hello Programmers, In this post, you will Know how to solve HackerRank Sherlock and Anagrams Solution. This problem is a part of the HackerRank Algorithms Series.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.
HackerRank Sherlock and Anagrams Solution
Task
Two strings are anagrams of each other if the letters of one string can be rearranged to form the other string. Given a string, find the number of pairs of substrings of the string that are anagrams of each other.
Example
s = mom
The list of all anagrammatic pairs is [m, m], [mo, om] at positions [[0], [2]], [[0, 1], [1, 2]] respectively.
Function Description
Complete the function sherlockAndAnagrams in the editor below.
sherlockAndAnagrams has the following parameter(s):
- string s: a string
Returns
- int: the number of unordered anagrammatic pairs of substrings in s.
Input Format
The first line contains an integer q, the number of queries.
Each of the next q lines contains a string s to analyze.
Constraints
- 1 <= q <= 10
- 2 <= length of s <= 100
- s contains only lowercase letters in the range ascii[a–z].
Sample Input 0
2 abba abcd
Sample Output 0
4 0
Explanation 0
The list of all anagrammatic pairs is [a, a], [ab, ba], [b, b] and [abb, bba] at positions [[0], [3]], [[0, 1], [2, 3]], [[1], [2]] and [[0, 1, 2], [1, 2, 3]] respectively.
No anagrammatic pairs exist in the second query as no character repeats.
Sample Input 1
2 ifailuhkqq kkkk
Sample Output 1
3 10
Explanation 1
For the first query, we have anagram pairs [i, i], [q, q] and [ifa, fai] at positions [[0], [3]], [[8], [9]] and [[0, 1, 2], [1, 2, 3]] respectively.
For the second query:
There are 6 anagrams of the form [k, k] at positions [[0], [1]], [[0], [2]], [[0], [3]], [[1], [2]], [[1], [3]] and [[2], [3]].
There are 3 anagrams of the form [kk, kk] at positions [[0, 1], [1, 2]], [[0, 1], [2, 3]] and [[1, 1], [2, 3]].
There is 1 anagram of the form [kkk, kkk] at position [[0, 1, 2], [1, 2, 3]].
Sample Input 2
1 cdcd
Sample Output 2
5
Explanation 2
There are two anagrammatic pairs of length 1: [c, c] and [d, d].
There are three anagrammatic pairs of length 2: [cd, dc], [cd, cd], [dc, cd] at positions [[0, 1], [1, 2]], [[0, 1], [2, 3]], [[1, 1], [2, 3]] respectively.
HackerRank Sherlock and Anagrams Solutions
Sherlock and Anagrams Solution 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;
}Sherlock and Anagrams Solution in Cpp
#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;
}Sherlock and Anagrams Solution 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);
}
}
}Sherlock and Anagrams Solution in Python
n=input()
for _ in xrange(n):
s=list(raw_input())
l=len(s)
count=0
for i in xrange(1,l):
dic={}
for j in xrange(l-i+1):
t=str(sorted(s[j:j+i]))
k=dic.setdefault(t,0)
dic[t]+=1
for j in dic:
#print j,dic[j]
count+=((dic[j])*(dic[j]-1))/2
print countSherlock and Anagrams Solution using JavaScript
function generateSubstrs(input){
var substrings = [];
for(var i=0;i<input.length;i++){
for(var j=1; i + j <= input.length;j++){
//3N operations on current substring
substrings.push(input.substr(i, j).split('').sort());
}
}
// O(nlogn) preprocessing step to help figure out anagram pairs
substrings.sort();
return substrings.map(function(el){return el.join('')});
}
function processData(input) {
input = input.split('\n');
for(var i=1;i<input.length;i++){
var subs = generateSubstrs(input[i]);
var k = 0;
var count = 0;
// O(N^2) iteration through all substrings.
while(k<subs.length){
var z = k+1;
while(subs[k] === subs[z]){
count ++;
z ++;
}
k ++;
}
console.log(count);
}
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});Sherlock and Anagrams Solution in Scala
import java.util.Scanner;
object Solution {
val sc = new Scanner(System.in)
def solve(s: String, len: Int): Long =
(0 to s.length - len).
map(i => s.substring(i, i + len).sortWith((a, b) => a < b)).
groupBy(x => x).map(_._2.size).filter(_ > 1).
map(x => x * (x - 1) / 2).sum
def solve(s: String): Long =
(1 until s.length).map(l => solve(s, l)).sum
def main(args: Array[String]) {
(0 until sc.nextLine().toInt).
map(_ => solve(sc.nextLine())).
foreach(println)
}
}Sherlock and Anagrams Solution in Pascal
(* Enter your code here. Read input from STDIN. Print output to STDOUT *)
uses math;
const
tfi = '';//arangramss.inp';
tfo = '';//arangramss.out';
var
fi,fo : text;
t,n,res : longint;
s : array[0..100,'a'..'z'] of longint;
st : string;
procedure input;
begin
readln(fi,st);
end;
procedure work;
var
i,j,k : longint;
ok : boolean;
ch : char;
begin
res:=0;n:=length(st);
for i:=1 to n do
for ch:='a' to 'z' do
if ch=st[i] then s[i,ch]:=s[i-1,ch]+1
else s[i,ch]:=s[i-1,ch];
for i:=1 to n-1 do
for j:=i+1 to n do
for k:=1 to i do
begin
ok:=true;
for ch:='a' to 'z' do
if s[i,ch]-s[i-k,ch]<>s[j,ch]-s[j-k,ch] then
begin
ok:=false;
break;
end;
if ok then inc(res);
end;
writeln(fo,res);
end;
begin
assign(fi,tfi);reset(fi);
assign(fo,tfo);rewrite(fo);
readln(fi,t);
while t>0 do
begin
input;
work;
dec(t);
end;
close(fi);close(fo);
end.
Disclaimer: This problem (Sherlock and Anagrams) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.