Skip to content

893. Groups of Special-Equivalent Strings 👎

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int numSpecialEquivGroups(vector<string>& words) {
    unordered_set<string> set;

    for (const string& word : words) {
      string even;
      string odd;
      for (int i = 0; i < word.length(); ++i)
        if (i % 2 == 0)
          even += word[i];
        else
          odd += word[i];
      ranges::sort(even);
      ranges::sort(odd);
      set.insert(even + odd);
    }

    return set.size();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int numSpecialEquivGroups(String[] words) {
    Set<String> set = new HashSet<>();

    for (final String word : words) {
      String even = "";
      String odd = "";
      for (int i = 0; i < word.length(); ++i)
        if (i % 2 == 0)
          even += word.charAt(i);
        else
          odd += word.charAt(i);
      char[] evenCharArray = even.toCharArray();
      char[] oddCharArray = odd.toCharArray();
      Arrays.sort(evenCharArray);
      Arrays.sort(oddCharArray);
      set.add(new String(evenCharArray) + new String(oddCharArray));
    }

    return set.size();
  }
}

1
2
3
4
class Solution:
  def numSpecialEquivGroups(self, words: list[str]) -> int:
    return len({''.join(sorted(word[::2])) + ''.join(sorted(word[1::2]))
                for word in words})