HackerRank Sherlock and Anagrams problem solution

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

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