Java solution for Sherlock and Anagrams Problem
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.
Example 1 :
Input:
s = abba
Output :
4
The list of all anagrammatic pairs is [a, a], [ab, ba], [b, b] and [abb, bba] at positions [[0], [3]], [[0, 1], [2, 3]], [[1], [2]], [[0, 1, 2], [1, 2, 3]].
Example 2 :
s = abcd
No anagrammatic pairs exist in the second query as no character repeats.
In this problem, we have to find that given String is anagram or not. But we have to find in sub string. So lets see solution and its explanation.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
import java.util.Map.Entry;
class Result {
public static int sherlockAndAnagrams(String s) {
int pair = 0;
Map<String, Integer> map = new HashMap<>();
int currentPair = 1;
while (currentPair != s.length()) {
for (int i = 0; i < s.length(); i++) {
if (( i+currentPair) <= s.length()) {
String subString = s.substring(i, i+currentPair);
char[] array = subString.toCharArray();
Arrays.sort(array);
String sorted = String.valueOf(array);
if (map.containsKey(sorted)) {
map.put(sorted, map.get(sorted)+1);
} else {
map.put(sorted, 1);
}
}
}
currentPair++;
}
for (Entry<String, Integer> data : map.entrySet()) {
pair += data.getValue()*(data.getValue()-1) / 2;
}
return pair;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int q = Integer.parseInt(bufferedReader.readLine().trim());
IntStream.range(0, q).forEach(qItr -> {
try {
String s = bufferedReader.readLine();
int result = Result.sherlockAndAnagrams(s);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
bufferedReader.close();
bufferedWriter.close();
}
}
Solution Explanation :
- For solving this problem, we have to create pair of string from 1 to string length -1. ex, String = java so we have to create following pair and check if anagram is applicable or not.
- pair of 1 character : [j, a], [j, v], [j, a], [a, v], [a, a], [v, a]
- pair of 2 characters : [ja, av], [ja, va], [av, va]
- pair of 3 characters : [jav, ava]
- Declare and Initialize HashMap<String, Integer>, So we can count pair. Declare two int variable pair and currentPair, initialize with 0 and 1.
- Using while loop, we create pair of Characters until string length.
- Traverse through 0 to string length.
- Write if condition for checking our pair not cause StringIndexOutOfBoundsException.
- Now we have getting our pair (substring).
- Convert substring into character array, and sort character array, and then convert character array to String again.
- Now check if map contains our pair (substring), then increment map value by 1 otherwise pair as new key and value as 1.
- After completing put all pair in map, Loop through map and apply following formula for getting total pair.
- pair += data.getValue()*(data.getValue()-1) / 2;
- Return pair.
Happy Coding. Happy Learning.
Other Hackerrank solutions in Java :
Comments
Post a Comment