# 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](https://leetcode.com/problems/groups-of-special-equivalent-strings/))

## 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:

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

## Examples

Example 1:

```text
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:

```text
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:

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

For example:

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

For:

```text
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:

```python
word[::2]
```

2. Extract characters at odd indices:

```python
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:

```text
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:

```text
("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:

```text
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

```python
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:

```python
groups = set()
```

For each word:

```python
for word in words:
```

we collect and sort even-indexed characters:

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

and odd-indexed characters:

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

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

```python
groups.add((even, odd))
```

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

```python
return len(groups)
```

## Testing

```python
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 |