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:

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

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:

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

For "abcd":

For "cdab":

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:

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])

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: