# Groups of Special-Equivalent Strings **Difficulty:** MEDIUM [External](https://leetcode.com/problems/groups-of-special-equivalent-strings) Canonical: https://scaleengineer.com/dsa/problems/groups-of-special-equivalent-strings **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array, Hash Table, String --- ## Problem You are given an array of strings of the same length `words`. In one **move**, you can swap any two even indexed characters or any two odd indexed characters of a string `words[i]`. Two strings `words[i]` and `words[j]` are **special-equivalent** if after any number of moves, `words[i] == words[j]`. * For example, `words[i] = "zzxy"` and `words[j] = "xyzz"` are **special-equivalent** because we may make the moves `"zzxy" -> "xzzy" -> "xyzz"`. A **group of special-equivalent strings** from `words` is a non-empty subset of words such that: * Every pair of strings in the group are special equivalent, and * The group is the largest size possible (i.e., there is not a string `words[i]` not in the group such that `words[i]` is special-equivalent to every string in the group). Return _the number of **groups of special-equivalent strings** from_ `words`. **Example 1:** **Input:** words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"] **Output:** 3 **Explanation:** One group is ["abcd", "cdab", "cbad"], since they are all pairwise special equivalent, and none of the other strings is all pairwise special equivalent to these. The other two groups are ["xyzz", "zzxy"] and ["zzyx"]. Note that in particular, "zzxy" is not special equivalent to "zzyx". **Example 2:** **Input:** words = ["abc","acb","bac","bca","cab","cba"] **Output:** 3 **Constraints:** * `1 <= words.length <= 1000` * `1 <= words[i].length <= 20` * `words[i]` consist of lowercase English letters. * All the strings are of the same length. # Approaches ## Canonical Representation by Sorting This approach identifies special-equivalent strings by creating a canonical form for each string. Two strings are special-equivalent if and only if the multiset of their even-indexed characters are the same, and the multiset of their odd-indexed characters are the same. We can represent these multisets canonically by sorting them. For each word, we separate its characters into two lists based on their index (even or odd), sort both lists, and then concatenate them. This new string serves as a unique identifier for its equivalence group. We use a HashSet to count the number of unique canonical forms, which corresponds to the number of groups. **Time:** O(N * L log L), where N is the number of words and L is the length of each word. For each of the N words, we iterate through its L characters (O(L)), sort two arrays of size approximately L/2 (2 * O(L/2 log(L/2)) which simplifies to O(L log L)), and create a new string (O(L)). The dominant step is sorting, leading to O(L log L) per word. · **Space:** O(N * L). The `HashSet` can store up to N unique canonical strings, each of length L. In the worst case (all words are in different groups), this requires O(N * L) space. Additionally, O(L) temporary space is used for the character arrays for each word. **Pros:** Conceptually straightforward and easy to implement.; Directly models the problem definition where order doesn't matter within even/odd positions. **Cons:** Less efficient than a counting-based approach, especially as the length of the strings (L) increases, due to the O(L log L) sorting step. ### Explanation The core idea is that allowing swaps of any two even-indexed characters (or odd-indexed characters) means we can achieve any permutation of those characters. Therefore, two strings are special-equivalent if they have the same characters at even positions and the same characters at odd positions, irrespective of their order. To check this, we follow the algorithm to create a canonical representation for each string and count the unique ones. ```java import java.util.Arrays; import java.util.HashSet; import java.util.Set; class Solution { public int numSpecialEquivGroups(String[] words) { Set seen = new HashSet<>(); for (String word : words) { int n = word.length(); char[] evenChars = new char[(n + 1) / 2]; char[] oddChars = new char[n / 2]; for (int i = 0; i < n; i++) { if (i % 2 == 0) { evenChars[i / 2] = word.charAt(i); } else { oddChars[i / 2] = word.charAt(i); } } Arrays.sort(evenChars); Arrays.sort(oddChars); String canonical = new String(evenChars) + new String(oddChars); seen.add(canonical); } return seen.size(); } } ``` ### Algorithm * Initialize a `HashSet` to store the unique canonical representations. * Iterate through each `word` in the input array `words`. * For each `word`, create two character arrays: one for characters at even indices and one for characters at odd indices. * Populate these two arrays by iterating through the `word`. * Sort both character arrays alphabetically. * Create a new string by concatenating the sorted even-indexed characters and the sorted odd-indexed characters. * Add this canonical string to the `HashSet`. * After processing all words, the size of the `HashSet` is the number of special-equivalent groups. ## Canonical Representation by Character Counting This approach improves upon the sorting method by using frequency counting, which is more efficient for a fixed alphabet. Instead of sorting the even and odd indexed characters, we count the occurrences of each character ('a' through 'z') for both sets. The canonical representation is then formed by serializing these two frequency counts into a single string. For example, we can concatenate the 26 counts for even-indexed characters followed by the 26 counts for odd-indexed characters. This unique string key represents the equivalence group. We use a HashSet to count the number of unique keys. **Time:** O(N * L), where N is the number of words and L is the length of each word. For each of the N words, we iterate through its L characters to populate the count arrays (O(L)). Creating the key from the count arrays takes constant time, as the alphabet size is fixed at 26 (O(1)). Thus, the total time is dominated by iterating through the words. · **Space:** O(N * C), where N is the number of words and C is the length of the canonical key. The key length C is constant (related to the alphabet size, 26). In the worst case, the `HashSet` stores N distinct keys, leading to O(N) space. The temporary space for the count arrays for each word is O(1) (2 * 26 integers). **Pros:** More efficient than the sorting approach, with a linear time complexity.; Scales better with the length of the strings (L). **Cons:** The construction of the canonical key might seem slightly less direct than sorting, but is a standard technique for anagram-style problems. ### Explanation Since the characters are limited to lowercase English letters, we can use an array of size 26 as a frequency map instead of sorting. This avoids the O(L log L) complexity of sorting. The canonical representation is built from the character counts, which uniquely define the multiset of characters for both even and odd positions. We then count the number of unique representations to find the number of groups. ```java import java.util.Arrays; import java.util.HashSet; import java.util.Set; class Solution { public int numSpecialEquivGroups(String[] words) { Set seen = new HashSet<>(); for (String word : words) { int[] evenCounts = new int[26]; int[] oddCounts = new int[26]; for (int i = 0; i < word.length(); i++) { if (i % 2 == 0) { evenCounts[word.charAt(i) - 'a']++; } else { oddCounts[word.charAt(i) - 'a']++; } } // Serialize the count arrays into a canonical string key. // Arrays.toString() provides a consistent string representation. String key = Arrays.toString(evenCounts) + Arrays.toString(oddCounts); seen.add(key); } return seen.size(); } } ``` ### Algorithm * Initialize a `HashSet` to store the unique canonical keys. * Iterate through each `word` in the input array `words`. * For each `word`, create two integer arrays of size 26, `evenCounts` and `oddCounts`, initialized to zero. * Iterate through the `word` with index `i` and character `c`: * If `i` is even, increment `evenCounts[c - 'a']`. * If `i` is odd, increment `oddCounts[c - 'a']`. * Serialize the two count arrays into a single, unique string key. A simple way is to convert the arrays to strings and concatenate them. * Add this key to the `HashSet`. * After processing all words, the size of the `HashSet` is the answer. # Solutions ### Java ```java class Solution { public int numSpecialEquivGroups ( String [] words ) { Set < String > s = new HashSet <>(); for ( String word : words ) { s . add ( convert ( word )); } return s . size (); } private String convert ( String word ) { List < Character > a = new ArrayList <>(); List < Character > b = new ArrayList <>(); for ( int i = 0 ; i < word . length (); ++ i ) { char ch = word . charAt ( i ); if ( i % 2 == 0 ) { a . add ( ch ); } else { b . add ( ch ); } } Collections . sort ( a ); Collections . sort ( b ); StringBuilder sb = new StringBuilder (); for ( char c : a ) { sb . append ( c ); } for ( char c : b ) { sb . append ( c ); } return sb . toString (); } } ``` ### CPP ```cpp class Solution { public: int numSpecialEquivGroups ( vector < string >& words ) { unordered_set < string > s ; for ( auto & word : words ) { string a = "" , b = "" ; for ( int i = 0 ; i < word . size (); ++ i ) { if ( i & 1 ) a += word [ i ]; else b += word [ i ]; } sort ( a . begin (), a . end ()); sort ( b . begin (), b . end ()); s . insert ( a + b ); } return s . size (); } }; ``` ### Python ```python class Solution : def numSpecialEquivGroups ( self , words : List [ str ]) -> int : s = { '' . join ( sorted ( word [:: 2 ]) + sorted ( word [ 1 :: 2 ])) for word in words } return len ( s ) ```