Sherlock and Anagrams – HackerRank Solution

In this post, we will solve Sherlock and Anagrams HackerRank Solution. This problem (Sherlock and Anagrams) is a part of HackerRank Problem Solving series.

Solution – Sherlock and Anagrams – HackerRank Solution

C++

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

map<string, int>::iterator it;

int main() {
    int T;
    cin>>T;
    while(T--) {
        if(T < 0) {
            break;
        }
        string s;
        cin>>s;
        map<string, int> string_map;
        // Look at all substrings of s
        for(int i = 0; i < s.length(); i++) {
            for(int j = 1; j <= s.length()-i; j++) {
                // Sort the substring (lexographically increasing)
                char letter = 'a';
                string substring, sorted_substring;
                substring = s.substr(i, j);
                for(int k = 0; k < 27; k++) {
                    for(int l = 0; l < substring.length(); l++) {
                        if(substring[l] == letter) {
                            sorted_substring += letter;
                        }
                    }
                    letter++;
                }
                // Count the number of occurences of the (sorted) substring
                if(string_map.count(sorted_substring) == 0) {
                    string_map[sorted_substring] = 0;
                } else {
                    string_map[sorted_substring] += 1;
                }
            }
        }
        int count = 0;
        // For every substring that appears more than once, the number of "unordered anagramic pairs"
        // is equal to n(n+1)/2, where n is the number of occurences 
        for (it = string_map.begin(); it != string_map.end(); it++)
        {
            int value = it->second;
            if(value > 0) {
                count += (value*(value+1)/2);
            }
        }
        cout<<count<<"\n";
    }
    return 0;
}

Python

cases = int(input())
for caseNo in range(cases):
    s = input()
    n = len(s)
    res = 0
    for l in range(1, n):
        cnt = {}
        for i in range(n - l + 1):
            subs = list(s[i:i + l])
            subs.sort()
            subs = ''.join(subs)
            if subs in cnt:
                cnt[subs] += 1
            else:
                cnt[subs] = 1
            res += cnt[subs] - 1
    print(res)
            

Java

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

public class Solution {

    // Complete the sherlockAndAnagrams function below.
    public static final int ALPHABET_CNT = 26;

    static boolean isAnagrams(String s1, String s2) {

        char[] chCnt1 = new char[ALPHABET_CNT];
        char[] chCnt2 = new char[ALPHABET_CNT];


        for (int i = 0, n = s1.length(); i < n; i++) {
            chCnt1[s1.charAt(i) - 97] += 1;
            chCnt2[s2.charAt(i) - 97] += 1;
        }

        for (int i = 0; i < ALPHABET_CNT; i++) {
            if (chCnt1[i] != chCnt2[i]) {
                return false;
            }
        }

        return true;
    }

    // Complete the sherlockAndAnagrams function below.
    static int sherlockAndAnagrams(String s) {
        int cnt = 0;
        for (int i = 1, n = s.length(); i < n; i++) {
            List<String> subsetList = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (i + j <= n) {
                    subsetList.add(s.substring(j, i + j));
                }
            }

            for (int k = 0, size = subsetList.size(); k < size; k++) {
                for (int l = k + 1; l < size; l++) {
                    if (isAnagrams(subsetList.get(k), subsetList.get(l))) {
                        cnt++;
                    }
                }
            }
        }


        return cnt;
    }

    private static final Scanner scanner = new Scanner(System.in);

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

        int q = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int qItr = 0; qItr < q; qItr++) {
            String s = scanner.nextLine();

            int result = sherlockAndAnagrams(s);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}

Note: This problem (Sherlock and Anagrams) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.