In this HackerRank Sherlock and Anagrams Interview preparation kit problem you have Given a string, find the number of pairs of substrings of the string that are anagrams of each other.


HackerRank Sherlock and Anagrams Interview Preparation kit solution


Problem solution in Python programming.

from collections import Counter

def all_substrs(s):
    return [[s[j:j+i] for j in range(len(s) - i + 1)] for i in range(1, len(s))]

def countem(ll):
    c = Counter()
    s = 0
    for lst in ll:
        for e in lst:
            q = ''.join(sorted(e))
            c[q] += 1
    for e in c:
        s += int(c[e]*(c[e]-1)/2)
    return s
    
    
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        s = input()
        print(countem(all_substrs(s)))



Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int i=0; i<T; ++i){
            String str = sc.next().trim();
            System.out.println(numofAnagram(str));
        }
    }
    
    public static int numofAnagram(String str){
        int total = 0;
        for(int i=1; i<str.length(); ++i){
            int[] tmpstr = new int[26];
            
            for(int j=i; j>=0; --j){
                tmpstr[str.charAt(j)-'a']++;
                
                for(int k=0; k<j; ++k){
                    int[] chars = new int[26];
                    int x = k;
                    int count =0;
                    while(count<=i-j){
                        ++chars[str.charAt(x)-'a'];
                        ++x;
                        ++count;
                    }
                    boolean flag = true;
                    for(x=0; x<26; ++x){
                        if(tmpstr[x]!=chars[x]){
                            flag = false;
                            break;
                        }
                    }
                    if(flag) ++total;   
                }
                
            }
        }
        return total;
    }
}


Problem solution in C++ programming.

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

int main() {
  int cases;
  scanf("%d", &cases);
  getchar();
  while (cases--) {
    unordered_map<string, int> mp;
    string s;
    getline(cin, s);
    int n = s.size();
    for (int len = 1; len < n; ++len) {
      for (int i = 0; i <= n - len; ++i) {
        string t = s.substr(i, len);
        sort(t.begin(), t.end());
        mp[t]++;
      }
    }
    long long ans = 0;
    for (auto t : mp) {
      ans += (long long)t.second * (t.second - 1) / 2;
    }
    printf("%lld\n", ans);
  }
  return 0;
}


Problem solution in C programming.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();

// Complete the sherlockAndAnagrams function below.
int check_anagram(char a[], char b[])
{
   int first[26] = {0}, second[26] = {0}, c = 0;

   while (a[c] != '\0') {
      first[a[c]-'a']++;
      c++;
   }
   c = 0;
   while (b[c] != '\0') {
      second[b[c]-'a']++;
      c++;
   }

   for (c = 0; c < 26; c++) {
      if (first[c] != second[c])
         return 0;
   }

   return 1;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        char s[100];
        char sub1[100] = {0};
        char sub2[100] = {0};
        scanf("%s", s);

        int count = 0;
        for (int len = 1; len < strlen(s); len++) {
            memset(sub1, 0, len);
            for (int i = 0; i < strlen(s) - len; i++) {
                strncpy(sub1, &s[i], len);
                memset(sub2, 0, len);
                for (int j = i + 1; j < strlen(s) - len + 1; j++) {
                    strncpy(sub2, &s[j], len);
                    if (check_anagram(sub1, sub2) == 1) {
                        count++;
                    }  
                }
            }     
        }

        printf("%d\n", count);


}

return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }

    data = realloc(data, data_length);

    return data;
}


Problem solution in JavaScript programming.

/*
Generate all substrings in O(N^2). It is quadratic because the total number of operations is the sum of the series n, n-1, n-2 .... 1
*/
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);
});