Groups of Special-Equivalent Strings

Med

#0847Time: 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.

Algorithms

Sorting

Data structures

Array Hash Table String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

Initialize a HashSet<String> 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.

Walkthrough

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.

1import java.util.Arrays;2import java.util.HashSet;3import java.util.Set;4 5class Solution {6    public int numSpecialEquivGroups(String[] words) {7        Set<String> seen = new HashSet<>();8        for (String word : words) {9            int n = word.length();10            char[] evenChars = new char[(n + 1) / 2];11            char[] oddChars = new char[n / 2];12            13            for (int i = 0; i < n; i++) {14                if (i % 2 == 0) {15                    evenChars[i / 2] = word.charAt(i);16                } else {17                    oddChars[i / 2] = word.charAt(i);18                }19            }20            21            Arrays.sort(evenChars);22            Arrays.sort(oddChars);23            24            String canonical = new String(evenChars) + new String(oddChars);25            seen.add(canonical);26        }27        return seen.size();28    }29}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Initialize a HashSet<String> 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.

Walkthrough

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.

1import java.util.Arrays;2import java.util.HashSet;3import java.util.Set;4 5class Solution {6    public int numSpecialEquivGroups(String[] words) {7        Set<String> seen = new HashSet<>();8        for (String word : words) {9            int[] evenCounts = new int[26];10            int[] oddCounts = new int[26];11            12            for (int i = 0; i < word.length(); i++) {13                if (i % 2 == 0) {14                    evenCounts[word.charAt(i) - 'a']++;15                } else {16                    oddCounts[word.charAt(i) - 'a']++;17                }18            }19            20            // Serialize the count arrays into a canonical string key.21            // Arrays.toString() provides a consistent string representation.22            String key = Arrays.toString(evenCounts) + Arrays.toString(oddCounts);23            seen.add(key);24        }25        return seen.size();26    }27}

Complexity

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).

Trade-offs

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.

Solutions

Solution

1class 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 (); } }

1class 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 (); } };

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem