Groups of Special-Equivalent Strings — Medium Problem & Solution

Problem statement

You are given an array words of lowercase strings, all of the same length.

In one move you may pick a string and swap two of its characters whose indices are both even, or two whose indices are both odd. Two strings are special-equivalent when some sequence of moves turns one into the other. For example "kode" and "doke" are special-equivalent: swapping the even-indexed k and d turns one into the other.

A group of special-equivalent strings is a non-empty subset of words in which every pair is special-equivalent and that cannot be extended by any other string of words. Return the number of groups.

Example 1

Input: words = ["kode","doke","koed","edok"]
Output: 3
Explanation: `"kode"` and `"doke"` form one group; `"koed"` and `"edok"` each stand alone.

Example 2

Input: words = ["xyz","zyx","yxz"]
Output: 2

Example 3

Input: words = ["a","b","a"]
Output: 2

Constraints

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 20
• words[i] consists of lowercase English letters
• all strings in words have the same length

How to solve Groups of Special-Equivalent Strings

Swaps generate every permutation, so a string can reach exactly the strings whose even-indexed letters are a rearrangement of its own even-indexed letters and likewise for odd. The pair (multiset of even letters, multiset of odd letters) is therefore a complete invariant, and the groups are its distinct values.

Approach

1. For each word, count its letters at even indices and at odd indices separately (or sort each half).
2. Combine the two into one key, e.g. the 52 counts or sortedEven + "|" + sortedOdd.
3. Insert every key into a hash set.
4. Return the size of the set.

Why it works

Moves never carry a letter from an even index to an odd one, so the two multisets never change — equivalent strings share the key. Conversely, any two arrangements of the same multiset are connected by transpositions, so strings with the same key are equivalent. Special-equivalence is thus an equivalence relation whose classes are the key values.

Complexity

• Time — O(n · L) with counting (O(n · L log L) with sorting)
• Space — O(n · L)

Pitfalls

• Sorting the whole word is wrong — "ab" and "ba" have the same letters but are not equivalent.
• Separate the two halves in the key (a delimiter or fixed-size counts); concatenating unsorted halves of different words can collide otherwise.
• Duplicate words belong to the same group.

Reference solution

Python

from typing import List

def numSpecialEquivGroups(words: List[str]) -> int:
    seen = set()
    for w in words:
        seen.add((''.join(sorted(w[0::2])), ''.join(sorted(w[1::2]))))
    return len(seen)

JavaScript

var numSpecialEquivGroups = function(words) {
    var seen = new Set();
    for (var i = 0; i < words.length; i++) {
        var w = words[i];
        var ev = [], od = [];
        for (var j = 0; j < w.length; j++) {
            if (j % 2 === 0) ev.push(w[j]); else od.push(w[j]);
        }
        seen.add(ev.sort().join("") + "|" + od.sort().join(""));
    }
    return seen.size;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium