Hackerrank Sherlock and Anagrams Solution

.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

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.

For example , the list of all anagrammatic pairs is  at positions  respectively.

Function Description

Complete the function sherlockAndAnagrams in the editor below.  It must return an integer that represents the number of anagrammatic pairs of substrings in .

sherlockAndAnagrams has the following parameter(s):

• s: a string .

Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

The first line contains an integer , the number of queries.
Each of the next  lines contains a string  to analyze.

Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

String  contains only lowercase letters  ascii[a-z].

Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

For each query, return the number of unordered anagrammatic pairs.

Sample Input 0.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} 2abbaabcd

Sample Output 0.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} 40

Explanation 0.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

The list of all anagrammatic pairs is  and  at positions  and  respectively.

No anagrammatic pairs exist in the second query as no character repeats.

Sample Input 1.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} 2ifailuhkqqkkkk

Sample Output 1.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} 310

Explanation 1.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

For the first query, we have anagram pairs  and  at positions  and  respectively.

For the second query:
There are 6 anagrams of the form  at positions  and .
There are 3 anagrams of the form  at positions  and .
There is 1 anagram of the form  at position .

Sample Input 2.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0} 1cdcd

Sample Output 2.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} 5

Explanation 2.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}

There are two anagrammatic pairs of length :  and .
There are three anagrammatic pairs of length :  at positions  respectively.

Solution in java8

Approach 1.

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

public class Solution {

// Complete the sherlockAndAnagrams function below.

static int sherlockAndAnagrams(String str) {
Map<String, Integer> key2count = new HashMap<String, Integer>();
for (int i = 0; i < str.length(); i++) {
for (int j = i + 1; j <= str.length(); j++) {
String key = generateKey(str.substring(i, j));
if (!key2count.containsKey(key)) {
key2count.put(key, 0);
}
key2count.put(key, key2count.get(key) + 1);
}
}
return key2count.values().stream().mapToInt(count -> count * (count - 1) / 2).sum();
}

static String generateKey(String str) {
return str.chars().sorted().mapToObj(letter -> String.valueOf((char) letter)).collect(Collectors.joining());
}

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


Approach 2.

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.
static int sherlockAndAnagrams(String s) {
if (s.length() < 2) {
return 0;
}
int count = 0;
ArrayList<String> substrs = new ArrayList<>();
for (int i=0; i<s.length(); i++) {
for (int j=i; j<s.length(); j++) {
String sub = sortChar(s.substring(i, j+1));
for (String str : substrs ) {
if (str.equals(sub)) {
count++;
}
}
}
}

return count;
}

private static String sortChar(String str) {
if (str.length() == 1) {
return str;
}
char[] chars = str.toCharArray();
Arrays.sort(chars);

return new String(chars);
}

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


Approach 3.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
import java.lang.*;
public class Solution {

// Complete the sherlockAndAnagrams function below.
static int sherlockAndAnagrams(String s) {
int counter=0;
int n = s.length();
int c = 0;
while(counter < n-1)
{
String first = s.substring(0,counter+1);
int current = first.length();
//System.out.println("first "+first);
for(int i=0; i < n-current;i++)
{
String a = s.substring(i,Math.min(i + current, n));
char br[] = a.toCharArray();
Arrays.sort(br);
String firstsort=new String(br);
//System.out.println(a);
for(int j=i+1 ; j<=n-current; j++)
{
String b= s.substring(j,Math.min(j + current, n));
char[] ar = b.toCharArray();
Arrays.sort(ar);
String sorted = new String(ar);

//System.out.println("string b ="+b);
if(firstsort.equals(sorted))
{
c++;
}
}
}
counter++;
}
return c;
}

public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
sc.nextLine();
for (int qItr = 0; qItr < q; qItr++) {
String s = sc.nextLine();

int result = sherlockAndAnagrams(s);
System.out.println(result);

}

sc.close();
}
}


Solution in python3

Approach 1.

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import Counter

# Complete the sherlockAndAnagrams function below.
def sherlockAndAnagrams(s):
repo = {}
counter = 0
for l in range(1,len(s)): # length of substring
for i in range(len(s)-l+1):
key = frozenset(Counter(s[i:i+l]).items())
repo[key] = repo.get(key,0) + 1

for v in repo.values():
counter += v*(v-1)//2

return counter

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

q = int(input())

for q_itr in range(q):
s = input()

result = sherlockAndAnagrams(s)

fptr.write(str(result) + '\n')

fptr.close()


Approach 2.

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import Counter
import itertools

# Complete the sherlockAndAnagrams function below.
def sherlockAndAnagrams(s):
length = len(s)
allSubstrings = list(s) + list(itertools.chain.from_iterable([[s[j:j+i] for j in range(length-i+1)] for i in range(2, length)]))
substringsCount = [''.join(['{0}{1}'.format(x,y) for (x,y) in sorted(Counter(sub).items())]) for sub in allSubstrings]
return int(sum([v*(v-1)/2 for v in Counter(substringsCount).values()]))

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

q = int(input())

for q_itr in range(q):
s = input()

result = sherlockAndAnagrams(s)

fptr.write(str(result) + '\n')

fptr.close()


Approach 3.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the sherlockAndAnagrams function below.
def sherlockAndAnagrams(s):
freq = {i:[] for i in range(1, len(s) + 1)}
counter = 0
for i in range(1, len(s) + 1):
for j in range(0, len(s) - i + 1):
cur = sorted(s[j:i+j])
freq[i].append(cur)

for ind in freq:
ls = freq[ind]
for i in range(len(ls)):
for j in range(i + 1, len(ls)):
if ls[i] == ls[j]:
counter += 1

return counter

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

q = int(input())

for q_itr in range(q):
s = input()

result = sherlockAndAnagrams(s)

fptr.write(str(result) + '\n')

fptr.close()


Solution in cpp

Approach 1.

 #include<iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
map<string, int> m;
int main()
{
int t;
cin >> t;
while (t--)
{
m.clear();
string s;
cin >> s;
int len = (int)s.size();
for (int i = 0; i < len; i++)
{
for (int l = 1; i + l - 1 < len; l++)
{
string t = s.substr(i, l);
sort(t.begin(), t.end());
m[t]++;
}
}
long long ans = 0;
for (map<string, int>::iterator it = m.begin(); it != m.end(); ++it)
ans += (long long)(it->second) * (it->second - 1) / 2;
cout << ans << endl;
}
return 0;
}

Approach 2.


#include<iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;

map<string, int> m;

int main()
{
int t;
cin >> t;
while (t--)
{
m.clear();
string s;
cin >> s;
int len = (int)s.size();
for (int i = 0; i < len; i++)
{
for (int l = 1; i + l - 1 < len; l++)
{
string t = s.substr(i, l);
sort(t.begin(), t.end());
m[t]++;
}
}
long long ans = 0;
for (map<string, int>::iterator it = m.begin(); it != m.end(); ++it)
ans += (long long)(it->second) * (it->second - 1) / 2;
cout << ans << endl;
}
return 0;
}

Approach 3.

#include<iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
map<string, int> anag;
int main()
{
int T;
cin >> T;
while (T--)
{
anag.clear();
unsigned long long int answer = 0;
string str;
cin >> str;
for (int i = 0; i < str.size(); i++)
{
for (int j= 1; i + j - 1 < str.size(); j++)
{
string sub = str.substr(i, j);
sort(sub.begin(), sub.end());
anag[sub]++;
}
}
for (map<string, int>::iterator it = anag.begin(); it != anag.end(); ++it)
answer += (it->second) * (it->second - 1) / 2;
cout << answer << endl;
}
return 0;
}

Subscribe to The Poor Coder | Algorithm Solutions

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]
Subscribe