Watch 10 video solutions for Groups of Special-Equivalent Strings, a medium level problem involving Array, Hash Table, String. This walkthrough by code_report has 2,486 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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].
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:
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 <= 10001 <= words[i].length <= 20words[i] consist of lowercase English letters.Problem Overview: You receive an array of strings. Two strings are special-equivalent if you can swap characters among even indices or among odd indices any number of times and transform one string into the other. The task is to count how many distinct groups of such equivalent strings exist.
Approach 1: Group by Sorted Characters (O(n * k log k) time, O(n * k) space)
The allowed swaps mean characters at even indices can rearrange among themselves, and characters at odd indices can rearrange among themselves. For each string, split characters into two buckets: even-indexed and odd-indexed. Sort both buckets independently and combine them into a canonical key such as sortedEven + '#' + sortedOdd. Insert this key into a hash set to track unique groups. If two strings produce the same key, they belong to the same special-equivalent group. This method relies on sorting to normalize both parity positions and uses a hash table or set for grouping.
Approach 2: Character Frequency Counting (O(n * k) time, O(n) space)
Sorting is not strictly necessary. Since characters only rearrange within parity groups, the exact order is irrelevant; only the counts matter. For each string, build two frequency arrays of size 26: one for even positions and one for odd positions. Concatenate the counts into a compact signature (for example, a tuple or string). Insert this signature into a hash set to represent the group. Two strings with identical even and odd frequency distributions must be special-equivalent. This avoids sorting entirely and reduces the complexity to linear time per string. The solution heavily uses array indexing and string processing.
Recommended for interviews: Character Frequency Counting is usually the expected solution. It demonstrates recognition that order does not matter within parity groups and reduces the cost from k log k sorting to linear counting. The sorting approach still works and is easier to implement quickly, which makes it a good starting point during interviews before optimizing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Group by Sorted Even/Odd Characters | O(n * k log k) | O(n * k) | Simpler implementation when sorting cost is acceptable |
| Character Frequency Counting | O(n * k) | O(n) | Optimal approach when string length is large and sorting overhead should be avoided |