893. Groups of Special-Equivalent Strings
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).
Returnthe 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.
From: LeetCode
Link: 893. Groups of Special-Equivalent Strings
Solution:
Ideas:
Key idea:
Two words are special-equivalent if the counts of letters at even indices match and the counts of letters at odd indices match.Signature representation:
For each word, build a “signature” of 52 counts:- First 26 slots → counts of each letter at even indices.
- Next 26 slots → counts of each letter at odd indices.
Grouping:
- If two words share the same signature, they belong to the same group.
- Otherwise, they form different groups.
Algorithm steps:
- Initialize a storage for signatures.
- For each word, compute its signature.
- Compare with existing signatures to see if it’s already present.
- If not present, add it as a new group.
- Count how many unique signatures exist.
Code:
static int equal52(const int *a, const int *b) {
for (int i = 0; i < 52; ++i) if (a[i] != b[i]) return 0;
return 1;
}
int numSpecialEquivGroups(char** words, int wordsSize) {
if (wordsSize <= 0) return 0;
// Store unique 52-int signatures (26 counts for even idx, 26 for odd idx)
int *sigs = (int *)malloc(wordsSize * 52 * sizeof(int));
int uniq = 0;
for (int i = 0; i < wordsSize; ++i) {
int sig[52] = {0};
// Build signature: counts by parity
for (int k = 0; words[i][k] != '\0'; ++k) {
int c = words[i][k] - 'a';
if ((k & 1) == 0) sig[c]++; // even positions
else sig[26 + c]++; // odd positions
}
// Check if this signature already exists
int found = 0;
for (int j = 0; j < uniq; ++j) {
if (equal52(sig, sigs + j * 52)) {
found = 1;
break;
}
}
if (!found) {
memcpy(sigs + uniq * 52, sig, 52 * sizeof(int));
++uniq;
}
}
free(sigs);
return uniq;
}