HackerRank Sherlock and Anagrams problem solution

In this HackerRank Sherlock and Anagrams Interview preparation kit 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.

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.

HackerRank Sherlock and Anagrams problem solution in Python.

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)))

Sherlock and Anagrams problem solution in Java.

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("%lldn", 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] != '') {
      first[a[c]-'a']++;
      c++;
   }
   c = 0;
   while (b[c] != '') {
      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("%dn", 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] = '';
    }

    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);
});