LeetCode 893: Groups of Special-Equivalent Strings

Problem Restatement

We are given an array words.

All strings have the same length.

In one move, we can swap two characters only if their indices have the same parity:

Swap type	Allowed?
Even index with even index	Yes
Odd index with odd index	Yes
Even index with odd index	No

Two strings are special-equivalent if one can be changed into the other using any number of these moves.

Return the number of special-equivalent groups. LeetCode defines a group as a largest possible set of words where every pair is special-equivalent. (leetcode.com)

Input and Output

Item	Meaning
Input	words, a list of strings
Output	Number of special-equivalent groups
String length	All strings have the same length
Characters	Lowercase English letters
Allowed move	Swap characters among indices of the same parity

Function shape:

def numSpecialEquivGroups(self, words: list[str]) -> int:
    ...

Examples

Example 1:

Input: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]
Output: 3

The groups are:

Group	Words
1	"abcd", "cdab", "cbad"
2	"xyzz", "zzxy"
3	"zzyx"

"abcd" and "cdab" are special-equivalent.

For "abcd":

Index parity	Characters
Even indices 0, 2	a, c
Odd indices 1, 3	b, d

For "cdab":

Index parity	Characters
Even indices 0, 2	c, a
Odd indices 1, 3	d, b

The even-position characters match as a multiset, and the odd-position characters also match as a multiset.

Example 2:

Input: words = ["abc","acb","bac","bca","cab","cba"]
Output: 3

These words form three special-equivalent groups.

First Thought: Compare Words Directly

A direct idea is to compare every pair of words and decide whether they are special-equivalent.

For two words, we could check whether the characters at even positions match after rearranging, and whether the characters at odd positions match after rearranging.

Then we could build groups from pairwise comparisons.

This works, but it is more complicated than necessary.

We only need the number of groups, so each word can be reduced to a canonical signature.

Key Insight

Allowed swaps never move a character from an even index to an odd index, or from an odd index to an even index.

So two words are special-equivalent exactly when:

1. Their even-indexed characters are the same multiset.
2. Their odd-indexed characters are the same multiset.

A convenient canonical signature is:

sorted even-index characters + separator + sorted odd-index characters

For example:

word = "abcd"
even-index characters = "ac"
odd-index characters  = "bd"
signature = "ac#bd"

For:

word = "cdab"
even-index characters = "ca"
odd-index characters  = "db"
signature = "ac#bd"

They have the same signature, so they are in the same group.

Algorithm

Create an empty set groups.

For each word:

1. Extract characters at even indices:

word[::2]

2. Extract characters at odd indices:

word[1::2]

3. Sort both parts.
4. Combine them into a tuple or string signature.
5. Add the signature to the set.

Return the size of the set.

Walkthrough

Use:

words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]

Build signatures:

Word	Even chars sorted	Odd chars sorted	Signature
"abcd"	"ac"	"bd"	("ac", "bd")
"cdab"	"ac"	"bd"	("ac", "bd")
"cbad"	"ac"	"bd"	("ac", "bd")
"xyzz"	"xz"	"yz"	("xz", "yz")
"zzxy"	"xz"	"yz"	("xz", "yz")
"zzyx"	"yz"	"xz"	("yz", "xz")

Unique signatures:

("ac", "bd")
("xz", "yz")
("yz", "xz")

So there are 3 groups.

Correctness

Allowed moves can permute characters among even indices freely, because any two even-indexed characters may be swapped. The same is true for odd indices.

Allowed moves cannot move a character between an even index and an odd index.

Therefore, a word's special-equivalence class is completely determined by the multiset of characters at even indices and the multiset of characters at odd indices.

The algorithm sorts the even-indexed characters and odd-indexed characters separately. Sorting gives a canonical representation of each multiset.

If two words produce the same signature, then their even-position multisets are equal and their odd-position multisets are equal. We can rearrange the even positions and odd positions separately to transform one word into the other, so they are special-equivalent.

If two words produce different signatures, then either their even-position multisets differ or their odd-position multisets differ. Since parity cannot change under allowed moves, they cannot be special-equivalent.

Thus, each unique signature corresponds to exactly one special-equivalent group, and counting unique signatures gives the correct answer.

Complexity

Let:

m = len(words)
L = len(words[0])

Metric	Value	Why
Time	O(m * L log L)	Each word sorts its even and odd characters
Space	O(m * L)	The set stores signatures

Since L <= 20, sorting is already efficient.

Implementation

class Solution:
    def numSpecialEquivGroups(self, words: list[str]) -> int:
        groups = set()

        for word in words:
            even = "".join(sorted(word[::2]))
            odd = "".join(sorted(word[1::2]))

            groups.add((even, odd))

        return len(groups)

Code Explanation

We store one signature per group:

groups = set()

For each word:

for word in words:

we collect and sort even-indexed characters:

even = "".join(sorted(word[::2]))

and odd-indexed characters:

odd = "".join(sorted(word[1::2]))

The tuple (even, odd) is the canonical signature:

groups.add((even, odd))

At the end, each distinct signature represents one special-equivalent group:

return len(groups)

Testing

def run_tests():
    s = Solution()

    assert s.numSpecialEquivGroups(
        ["abcd", "cdab", "cbad", "xyzz", "zzxy", "zzyx"]
    ) == 3

    assert s.numSpecialEquivGroups(
        ["abc", "acb", "bac", "bca", "cab", "cba"]
    ) == 3

    assert s.numSpecialEquivGroups(
        ["a", "b", "c", "a", "c", "c"]
    ) == 3

    assert s.numSpecialEquivGroups(
        ["aa", "aa"]
    ) == 1

    assert s.numSpecialEquivGroups(
        ["ab", "ba"]
    ) == 2

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Standard multi-group case	Checks even and odd signatures
All permutations of "abc"	Confirms parity matters
One-character words	Each unique letter forms a group
Duplicate identical words	Same group
"ab" and "ba"	Cannot swap even with odd