Groups of Special-Equivalent Strings — Problem & Solution
Groups of Special-Equivalent Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Groups of Special-Equivalent Strings is a medium coding problem on arrays, strings and hash table, asked in Amazon and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table, Sorting
- Asked at: Amazon, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array words of lowercase strings, all of the same length.
In one move you may pick a string and swap two of its characters whose indices are both even, or two whose indices are both odd. Two strings are special-equivalent when some sequence of moves turns one into the other. For example "kode" and "doke" are special-equivalent: swapping the even-indexed k and d turns one into the other.
A group of special-equivalent strings is a non-empty subset of words in which every pair is special-equivalent and that cannot be extended by any other string of words. Return the number of groups.
Example 1
Input: words = ["kode","doke","koed","edok"]
Output: 3
Explanation: `"kode"` and `"doke"` form one group; `"koed"` and `"edok"` each stand alone.
Example 2
Input: words = ["xyz","zyx","yxz"]
Output: 2
Example 3
Input: words = ["a","b","a"]
Output: 2
Constraints
1 <= words.length <= 10001 <= words[i].length <= 20words[i] consists of lowercase English lettersall strings in words have the same length
Hints for Groups of Special-Equivalent Strings
Hint 1
Moves only shuffle the even positions among themselves and the odd positions among themselves.
Hint 2
Any rearrangement of the even positions is reachable by swaps, and so is any rearrangement of the odd ones.
Hint 3
So two strings are equivalent exactly when their even-index letters form the same multiset and their odd-index letters do too — build that as a key and count distinct keys.
How to solve Groups of Special-Equivalent Strings
Swaps generate every permutation, so a string can reach exactly the strings whose even-indexed letters are a rearrangement of its own even-indexed letters and likewise for odd. The pair (multiset of even letters, multiset of odd letters) is therefore a complete invariant, and the groups are its distinct values.
Approach
- For each word, count its letters at even indices and at odd indices separately (or sort each half).
- Combine the two into one key, e.g. the 52 counts or
sortedEven + "|" + sortedOdd. - Insert every key into a hash set.
- Return the size of the set.
Why it works
Moves never carry a letter from an even index to an odd one, so the two multisets never change — equivalent strings share the key. Conversely, any two arrangements of the same multiset are connected by transpositions, so strings with the same key are equivalent. Special-equivalence is thus an equivalence relation whose classes are the key values.
Complexity
- Time —
O(n · L) with counting (O(n · L log L) with sorting) - Space —
O(n · L)
Pitfalls
- Sorting the whole word is wrong —
"ab"and"ba"have the same letters but are not equivalent. - Separate the two halves in the key (a delimiter or fixed-size counts); concatenating unsorted halves of different words can collide otherwise.
- Duplicate words belong to the same group.
Reference solution
Python
from typing import List
def numSpecialEquivGroups(words: List[str]) -> int:
seen = set()
for w in words:
seen.add((''.join(sorted(w[0::2])), ''.join(sorted(w[1::2]))))
return len(seen)Java
public static int numSpecialEquivGroups(String[] words) {
Set<String> seen = new HashSet<>();
for (String w : words) {
int[] cnt = new int[52];
for (int i = 0; i < w.length(); i++) cnt[(i % 2) * 26 + (w.charAt(i) - 'a')]++;
seen.add(Arrays.toString(cnt));
}
return seen.size();
}C++
int numSpecialEquivGroups(vector<string>& words) {
set<vector<int>> seen;
for (const string& w : words) {
vector<int> cnt(52, 0);
for (int i = 0; i < (int)w.size(); i++) cnt[(i % 2) * 26 + (w[i] - 'a')]++;
seen.insert(cnt);
}
return (int)seen.size();
}JavaScript
var numSpecialEquivGroups = function(words) {
var seen = new Set();
for (var i = 0; i < words.length; i++) {
var w = words[i];
var ev = [], od = [];
for (var j = 0; j < w.length; j++) {
if (j % 2 === 0) ev.push(w[j]); else od.push(w[j]);
}
seen.add(ev.sort().join("") + "|" + od.sort().join(""));
}
return seen.size;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.