Groups of Special-Equivalent Strings solution and explanation
9 more videos on this problem
LeetCode 99 Problem 2 - Groups of Special-Equivalent Strings (893)code_report · 9:40 · 2K views
LeetCode 893: Groups of Special Equivalent Strings - Interview Prep Ep 36Fisher Coder · 10:22 · 1K views
893. Groups of Special-Equivalent Strings | String questions | Coding Interview Questions SeriesRKSolTech · 20:05 · 457 views
893. Groups of Special-Equivalent Strings (Leetcode Easy)Programming Live with Larry · 7:52 · 386 views
Leetcode 893. Groups of Special-Equivalent StringsAYUSH GARG · 6:20 · 230 views
893. Groups of Special-Equivalent Strings - Daily Leetcode (Day 57)yeetcode · 4:04 · 216 views
Vol124 - Leetcode - Problem 893 - Groups of special - equivalent strings - Golang - Phỏng vấnYuh lập trình viên · 18:58 · 185 views
LeetCode | 893. Groups of Special-Equivalent Strings | RustSergio García Prado · 11:36 · 87 views
Leetcode 893. Groups of Special-Equivalent Strings (greedy)LetsCode · 7:49 · 40 views
No Sound Leetcode 893: Groups of Special-Equivalent StringsExtremeProgrammer · 1:29 · 14 views
The 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"andwords[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 thatwords[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.- All the strings are of the same length.
Approach overview
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 1: Group by Sorted Characters
This approach involves separating each word into two groups of characters: those at even indices and those at odd indices. By sorting the characters in each group and forming a tuple of the sorted results, we establish a unique signature for special-equivalent strings. We then use a set to keep track of unique signatures, as duplicate tuples will represent special-equivalent strings.
def numSpecialEquivGroups(words):
seen = set()
for word in words:
even_chars = sorted(word[::2])
odd_chars = sorted(word[1::2])
seen.add((tuple(even_chars), tuple(odd_chars)))
return len(seen)
if __name__ == "__main__":
words = ["abcd", "cdab", "cbad", "xyzz", "zzxy", "zzyx"]
print(numSpecialEquivGroups(words)) # Output: 3import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;
public class Solution {
public static int numSpecialEquivGroups(String[] words) {
Set<String> seen = new HashSet<>();
for (String word : words) {
char[] even = new char[word.length() / 2];
char[] odd = new char[(word.length() + 1) / 2];
int evenIndex = 0, oddIndex = 0;
for (int i = 0; i < word.length(); i++) {
if (i % 2 == 0) {
even[evenIndex++] = word.charAt(i);
} else {
odd[oddIndex++] = word.charAt(i);
}
}
Arrays.sort(even);
Arrays.sort(odd);
seen.add(new String(even) + new String(odd));
}
return seen.size();
}
public static void main(String[] args) {
String[] words = {"abcd", "cdab", "cbad", "xyzz", "zzxy", "zzyx"};
System.out.println(numSpecialEquivGroups(words)); // Output: 3
}
}#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
int numSpecialEquivGroups(vector<string>& words) {
unordered_set<string> seen;
for (const auto& word : words) {
string even, odd;
for (int i = 0; i < word.length(); ++i) {
if (i % 2 == 0) even += word[i];
else odd += word[i];
}
sort(even.begin(), even.end());
sort(odd.begin(), odd.end());
seen.insert(even + odd);
}
return seen.size();
}
int main() {
vector<string> words = {"abcd","cdab","cbad","xyzz","zzxy","zzyx"};
cout << numSpecialEquivGroups(words) << endl;
return 0;
}function numSpecialEquivGroups(words) {
let seen = new Set();
for (let word of words) {
let even = [];
let odd = [];
for (let i = 0; i < word.length; i++) {
if (i % 2 === 0) even.push(word[i]);
else odd.push(word[i]);
}
even.sort();
odd.sort();
seen.add(even.join('') + odd.join(''));
}
return seen.size;
}
let words = ["abcd", "cdab", "cbad", "xyzz", "zzxy", "zzyx"];
console.log(numSpecialEquivGroups(words)); // Output: 3;#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(char*)a) - (*(char*)b);
}
void sort_string(char *s) {
qsort(s, strlen(s), sizeof(char), cmp);
}
int numSpecialEquivGroups(char ** words, int wordsSize) {
int groupCount = 0;
char seen[1000][41];
int seenSize = 0;
for (int i = 0; i < wordsSize; ++i) {
char even[21] = {0}, odd[21] = {0};
int evenIndex = 0, oddIndex = 0;
for (int j = 0; words[i][j]; ++j) {
if (j % 2 == 0)
even[evenIndex++] = words[i][j];
else
odd[oddIndex++] = words[i][j];
}
sort_string(even);
sort_string(odd);
char signature[41];
snprintf(signature, sizeof(signature), "%s%s", even, odd);
int isNew = 1;
for (int k = 0; k < seenSize; ++k) {
if (strcmp(seen[k], signature) == 0) {
isNew = 0;
break;
}
}
if (isNew) {
strcpy(seen[seenSize++], signature);
groupCount++;
}
}
return groupCount;
}
int main() {
char *words[] = {"abcd","cdab","cbad","xyzz","zzxy","zzyx"};
int result = numSpecialEquivGroups(words, 6);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int NumSpecialEquivGroups(string[] words) {
HashSet<string> seen = new HashSet<string>();
foreach (string word in words) {
List<char> even = new List<char>();
List<char> odd = new List<char>();
for (int i = 0; i < word.Length; i++) {
if (i % 2 == 0) even.Add(word[i]);
else odd.Add(word[i]);
}
even.Sort();
odd.Sort();
seen.Add(string.Join(',', even) + string.Join(',', odd));
}
return seen.Count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
string[] words = {"abcd", "cdab", "cbad", "xyzz", "zzxy", "zzyx"};
Console.WriteLine(sol.NumSpecialEquivGroups(words)); // Output: 3
}
}The Python solution makes use of tuples to store sorted even and odd characters from each word, adding them to a set to determine distinct groups of special-equivalent strings.
Time Complexity: O(N * M log M) due to sorting the characters in each word.
Space Complexity: O(N * M) for storing the unique combinations of tuples in the set.
Approach 2: Character Frequency Counting
This approach uses character frequency counts rather than sorting. By counting occurrences of each character in even and odd positions separately, we can determine if two strings are special-equivalent. Each string creates two frequency maps (or equivalent structures), and these are combined into a single representation for comparison across all words.
def numSpecialEquivGroups(words):
seen = set()
for word in words:
even_count = [0] * 26
odd_count = [0] * 26
for i, char in enumerate(word):
if i % 2 == 0:
even_count[ord(char) - ord('a')] += 1
else:
odd_count[ord(char) - ord('a')] += 1
seen.add((tuple(even_count), tuple(odd_count)))
return len(seen)
if __name__ == "__main__":
words = ["abc", "acb", "bac", "bca", "cab", "cba"]
print(numSpecialEquivGroups(words)) # Output: 3import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;
public class Solution {
public static int numSpecialEquivGroups(String[] words) {
Set<String> seen = new HashSet<>();
for (String word : words) {
int[] evenCount = new int[26];
int[] oddCount = new int[26];
for (int i = 0; i < word.length(); i++) {
if (i % 2 == 0) {
evenCount[word.charAt(i) - 'a']++;
} else {
oddCount[word.charAt(i) - 'a']++;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
sb.append(evenCount[i]).append('-').append(oddCount[i]).append('-');
}
seen.add(sb.toString());
}
return seen.size();
}
public static void main(String[] args) {
String[] words = {"abc", "acb", "bac", "bca", "cab", "cba"};
System.out.println(numSpecialEquivGroups(words)); // Output: 3
}
}#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
using namespace std;
int numSpecialEquivGroups(vector<string>& words) {
unordered_set<string> seen;
for (const auto& word : words) {
int evenCount[26] = {0}, oddCount[26] = {0};
for (int i = 0; i < word.size(); i++) {
if (i % 2 == 0) evenCount[word[i] - 'a']++;
else oddCount[word[i] - 'a']++;
}
string signature = "";
for (int i = 0; i < 26; i++) {
signature += evenCount[i];
signature += oddCount[i];
}
seen.insert(signature);
}
return seen.size();
}
int main() {
vector<string> words = {"abc","acb","bac","bca","cab","cba"};
cout << numSpecialEquivGroups(words) << endl; // Output: 3
return 0;
}function numSpecialEquivGroups(words) {
let seen = new Set();
for (let word of words) {
let evenCount = new Array(26).fill(0);
let oddCount = new Array(26).fill(0);
for (let i = 0; i < word.length; i++) {
if (i % 2 === 0) evenCount[word.charCodeAt(i) - 97]++;
else oddCount[word.charCodeAt(i) - 97]++;
}
let signature = evenCount.join(',') + '|' + oddCount.join(',');
seen.add(signature);
}
return seen.size;
}
let words = ["abc", "acb", "bac", "bca", "cab", "cba"];
console.log(numSpecialEquivGroups(words)); // Output: 3;#include <stdio.h>
#include <string.h>
int numSpecialEquivGroups(char ** words, int wordsSize) {
char seen[1000][52] = {0};
int seenCount = 0;
for (int i = 0; i < wordsSize; i++) {
int even[26] = {0}, odd[26] = {0};
char signature[52];
for (int j = 0; words[i][j]; j++) {
if (j % 2 == 0)
even[words[i][j] - 'a']++;
else
odd[words[i][j] - 'a']++;
}
snprintf(signature, 52, "");
for (int k = 0; k < 26; k++) {
signature[2 * k] = even[k];
signature[2 * k + 1] = odd[k];
}
int found = 0;
for (int k = 0; k < seenCount; k++) {
if (memcmp(seen[k], signature, 52) == 0) {
found = 1;
break;
}
}
if (!found) {
memcpy(seen[seenCount++], signature, 52);
}
}
return seenCount;
}
int main() {
char *words[] = {"abc","acb","bac","bca","cab","cba"};
printf("%d\n", numSpecialEquivGroups(words, 6)); // Output: 3
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int NumSpecialEquivGroups(string[] words) {
HashSet<string> seen = new HashSet<string>();
foreach (string word in words) {
int[] evenCount = new int[26];
int[] oddCount = new int[26];
for (int i = 0; i < word.Length; i++) {
if (i % 2 == 0) evenCount[word[i] - 'a']++;
else oddCount[word[i] - 'a']++;
}
string signature = "";
for (int j = 0; j < 26; j++) {
signature += evenCount[j].ToString() + "," + oddCount[j].ToString() + ",";
}
seen.Add(signature);
}
return seen.Count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
string[] words = {"abc", "acb", "bac", "bca", "cab", "cba"};
Console.WriteLine(sol.NumSpecialEquivGroups(words)); // Output: 3
}
}In Python, the solution counts character frequencies at even and odd indexed positions, storing these frequencies as tuples in a set to identify unique groups of special-equivalent strings.
Time Complexity: O(N * M) since each character's place is evaluated.
Space Complexity: O(N * 52) for unique combinations of frequencies stored.
Approach 3: Default Approach
func numSpecialEquivGroups(words []string) int {
s := map[string]bool{}
for _, word := range words {
a, b := []rune{}, []rune{}
for i, c := range word {
if i&1 == 1 {
a = append(a, c)
} else {
b = append(b, c)
}
}
sort.Slice(a, func(i, j int) bool {
return a[i] < a[j]
})
sort.Slice(b, func(i, j int) bool {
return b[i] < b[j]
})
s[string(a)+string(b)] = true
}
return len(s)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Group by Sorted Characters | Time Complexity: O(N * M log M) due to sorting the characters in each word. |
| Character Frequency Counting | Time Complexity: O(N * M) since each character's place is evaluated. |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Groups of Special-Equivalent Strings easy or hard?
The problem is rated Medium because the key insight is recognizing that swaps only occur within even and odd positions. Once you convert each string into a canonical parity-based representation, grouping becomes straightforward using hashing.
Groups of Special-Equivalent Strings Python/Java solution
In Python, create two lists of size 26 for even and odd frequencies and store the tuple of counts in a set. In Java, use two int[26] arrays and convert them to a string key or use Arrays.toString. Both implementations group strings using a hash-based structure.
How to solve Groups of Special-Equivalent Strings in O(n)?
Process each string once and build two frequency arrays for even and odd positions. Combine these counts into a unique key and insert it into a hash set. Because each character is processed exactly once, the work per string is O(k), giving total complexity O(n * k).
What is the best approach for Groups of Special-Equivalent Strings?
The most efficient approach uses character frequency counting for even and odd indices separately. For each string, build two frequency arrays of size 26 and use them as a canonical signature in a hash set. Strings with identical parity frequency distributions belong to the same group. This runs in O(n * k) time where n is the number of strings and k is the string length.
Is Groups of Special-Equivalent Strings asked at Google/Amazon/Meta?
Problems involving string normalization and hash-based grouping appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require grouping strings by structural equivalence or canonical representation are common interview patterns.
What data structure is used in Groups of Special-Equivalent Strings?
A hash set or hash map stores canonical representations of each string's parity structure. Arrays are used for frequency counting of characters at even and odd indices, and strings or tuples act as unique group keys.
What is the time complexity of Groups of Special-Equivalent Strings?
The optimal solution runs in O(n * k) time using character frequency counting for even and odd indices. A simpler implementation sorts characters at even and odd positions separately, which costs O(n * k log k). Both approaches require storing group signatures in a hash set.