Groups of Special-Equivalent Strings LeetCode solution in Java

1
class Solution {
2
  public int numSpecialEquivGroups(String[] words) {
3
    if (words.length == 0 || words.length == 1) return words.length;
4

5
    // To store group sizes
6
    HashMap<String, Integer> hashmap = new HashMap<>();
7

8
    // To mark the strings already part of some groups
9
    boolean[] isGrouped = new boolean[words.length];
10

11
    for (int index = 0; index < words.length; index++) {
12
      if (isGrouped[index]) continue; // Already grouped
13
      String word = words[index];
14
      for (int j = index + 1; j < words.length; j++) {
15
        if (isGrouped[j]) continue; // Already grouped
16
        String string = words[j];
17

18
        // The idea is to store count of characters on even and odd indices
19
        // It is done by incrementing counts of characters in both even and odd maps respectively
20
        // Then compare the two strings by reducing the same count in both even and odd maps
21
        // If both the maps are empty at last, the two strings for a group
22
        HashMap<Character, Integer> evens = new HashMap<>();
23
        HashMap<Character, Integer> odds = new HashMap<>();
24
        boolean isSpecialEquivalent = true;
25

26
        for (int i = 0; i < word.length(); i++) {
27
          if (i % 2 == 0) {
28
            evens.put(word.charAt(i), evens.getOrDefault(word.charAt(i), 0) + 1);
29
          } else {
30
            odds.put(word.charAt(i), odds.getOrDefault(word.charAt(i), 0) + 1);
31
          }
32
        }
33

34
        for (int i = 0; i < string.length(); i++) {
35
          char character = string.charAt(i);
36
          if (i % 2 == 0) {
37
            if (!evens.containsKey(character)) {
38
              isSpecialEquivalent = false;
39
              break;
40
            }
41

42
            evens.put(character, evens.get(character) - 1);
43
            if (evens.get(character) == 0) evens.remove(character);
44
          } else {
45
            if (!odds.containsKey(character)) {
46
              isSpecialEquivalent = false;
47
              break;
48
            }
49

50
            odds.put(character, odds.get(character) - 1);
51
            if (odds.get(character) == 0) odds.remove(character);
52
          }
53
        }
54

55
        if (isSpecialEquivalent) {
56
          hashmap.put(word, hashmap.getOrDefault(word, 0) + 1);
57
          isGrouped[j] = true;
58
        }
59
      }
60

61
      // If no group is formed, the word alone forms a group of size 1
62
      if (!hashmap.containsKey(word)) hashmap.put(word, 1);
63
    }
64

65
    return hashmap.size();
66
  }
67
}