HackerRank Sherlock and Anagrams Solution

In this post, we will solve HackerRank Sherlock and Anagrams Problem Solution.

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.

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 [i fa, 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, 2], [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

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, 2], [2, 3]] respectively.

Table of Contents

Sherlock and Anagrams C Solution

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

char s[101];

int count_anagram(char* sa, char* sb, int maxl)
{
    int c[26], i, j, n = maxl;
    memset(c, 0, 26 * sizeof(int));
    for (i = 0; i < maxl; ++i)
    {
        c[sa[i] - 'a']++;
        c[sb[i] - 'a']--;
        for (j = 0; j < 26; ++j)
        {    
            if (c[j])
            {
                n--;
                break;
            }
        }  
    }
    return n;
}

int main() 
{
    int t = 0, i, j, l, c;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%s", s);
        l = strlen(s);
        c = 0;
        for (i = 0; i < l - 1; ++i)
        {
            for (j = i + 1; j < l; ++j)
            {
                c += count_anagram(s + i, s + j, l - j);
            }
        }
        printf("%d\n", c);
    }
    return 0;
}

Sherlock and Anagrams C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int countTimes(const vector<string> &v, string s) {
    int ret = 0;
    auto it = find(v.begin(), v.end(), s);
    while (it != v.end()) {
        ++ret;
        it = find(it + 1, v.end(), s);
    }
    return ret;
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int t;
    string s;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        cin >> s;
        vector<string> v;
        auto it = s.begin();
        auto it2 = it;
        int count = 0;
        while (it != s.end()) {
            it2 = it;
            while (it2 != s.end()) {
                string s2 = s.substr(it - s.begin(), it2 - it + 1);
                sort(s2.begin(), s2.end());
                count += countTimes(v, s2);
                v.push_back(s2);
                ++it2;
            }
            ++it;
        }
        cout << count << endl;
    }
    return 0;
}

Sherlock and Anagrams C Sharp Solution

using System;
using System.Collections.Concurrent;
using System.IO;
using System.Linq;
class Solution {
    static void Main(String[] args) {
        var numCases = Int32.Parse(Console.In.ReadLine());
        for (int i = 0; i < numCases; ++i)
            Solve(Console.In.ReadLine());
    }
    
    static void Solve(string str)
    {
        // Much simpler with Linq but avoid for perf.
        var dict = new ConcurrentDictionary<string, int>();
        Func<string, int, int> incrementFunc = (k,v) => v + 1;
        var len = str.Length;
        char[] dest = new char[len];
        var maxCount = len;
        for (int i = 0; i < len; ++i)
        {
            for (int count = 1; count <= maxCount; ++count)
            {
                str.CopyTo(i, dest, i, count);
                Array.Sort(dest, i, count);
                dict.AddOrUpdate(new String(dest, i, count), 1, incrementFunc);
            }
            --maxCount;
        }
        
        var numPairs = dict.Values.Where(v => v > 1).Sum(v => (v*(v-1))/2);
        Console.Out.WriteLine(numPairs);
    }
}

Sherlock and Anagrams Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'sherlockAndAnagrams' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts STRING s as parameter.
     */

    public static int sherlockAndAnagrams(String s) {
    // Write your code here
    Map<String, Integer> hashMap=new HashMap<String, Integer>();
    for(int i=0;i<s.length();i++){
        for(int j=i;j<s.length();j++){
            char[] c=s.substring(i, j+1).toCharArray();
            Arrays.sort(c);
            String k=new String(c);
            
            if(hashMap.containsKey(k)){
                hashMap.put(k,hashMap.get(k)+1);
            }
            else{
                hashMap.put(k,1);
            }
        }
    }
    int anagramPairs=0;
    for(String k : hashMap.keySet()){
        int v=hashMap.get(k);
        anagramPairs += (v*(v-1))/2;
    }
    return anagramPairs;

    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, q).forEach(qItr -> {
            try {
                String s = bufferedReader.readLine();

                int result = Result.sherlockAndAnagrams(s);

                bufferedWriter.write(String.valueOf(result));
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Sherlock and Anagrams JavaScript Solution

function processData(input) {
    //Enter your code here
    var lines = input.split("\n");
    //console.log(lines[0]);
    var cases = parseInt(lines[0]);
   
    for(var i=1;i<=cases;i++){
         var m=[];
        
        var len = lines[i].length;
        for(j=0;j<len;j++){
            for(k=1; j+k-1<len;k++){
                var t = lines[i].substr(j, k);
				t=t.split("").sort().join("");
                //console.log(lines[i]);
				//m[t]=m[t]+1;
                if(!m[t]){
                    m[t]=1;
                }
                else{
                    m[t]=m[t]+1;
                }
                //console.log(m[t]);
            }
        }
        var ans = 0;
		for (var it in m){
            //console.log(m[it]);
            ans += m[it] * (m[it]-1) / 2;
        }
			
		console.log(ans);
    }
} 

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 Python Solution

from math import factorial
n = int(input())

for _ in range(n):
    line = input()
    len_line = len(line)
    anagram_count = 0
    for i in range(1, len_line):
        count_dict = {}
        for j in range(len_line + 1 - i):
            cand = "".join(sorted(line[j:j+i]))
            if cand not in count_dict:
                count_dict[cand] = 1
            else:
                count_dict[cand]  = count_dict[cand] + 1
        for (k,v) in count_dict.items():
            if v>1:
                anagram_count = anagram_count + (v * (v-1))//2
    print(anagram_count)