-
Notifications
You must be signed in to change notification settings - Fork 2
/
UnorderedAnagrammaticPairsCounterImpl.java
52 lines (42 loc) · 1.63 KB
/
UnorderedAnagrammaticPairsCounterImpl.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package algorithms.implementations;
import algorithms.interfaces.UnorderedAnagrammaticPairsCounter;
import java.util.HashMap;
import java.util.Map;
/**
* https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem
* https://codereview.stackexchange.com/questions/169768/unordered-substring-anagrammatic-pairs
*/
public class UnorderedAnagrammaticPairsCounterImpl implements UnorderedAnagrammaticPairsCounter {
@Override
public int countUnorderedAnagrammaticPairs(String s) {
int count = 0;
for (int substringLength = 1; substringLength <= s.length(); substringLength++) {
Map<Map<Character, Integer>, Integer> substringsCounts = new HashMap<>();
for (int index = 0; index <= s.length() - substringLength; index++) {
String substring = s.substring(index, index + substringLength);
Map<Character, Integer> characterCounts = this.getCharacterCounts(substring);
Integer substringCounts = substringsCounts.get(characterCounts);
if (substringCounts == null) {
substringsCounts.put(characterCounts, 1);
} else {
count += substringCounts;
substringsCounts.put(characterCounts, substringCounts + 1);
}
}
}
return count;
}
@Override
public Map<Character, Integer> getCharacterCounts(String s) {
Map<Character, Integer> characterCounts = new HashMap<>();
for (char c : s.toCharArray()) {
Integer characterCount = characterCounts.get(c);
if (characterCount == null) {
characterCounts.put(c, 1);
} else {
characterCounts.put(c, characterCount + 1);
}
}
return characterCounts;
}
}