Groups of Special-Equivalent Strings

medium hash set sorting string

Problem

You are given an array of strings words, all of the same length. Two strings are special-equivalent if you can swap any two characters at even indices, or any two characters at odd indices, repeatedly, to turn one into the other. A group of special-equivalent strings is a maximal subset where every pair is special-equivalent. Return the number of such groups.

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

Output3

["abcd", "cdab", "cbad"] form one group and ["xyzz", "zzxy"] and ["zzyx"] split into two groups, giving 3 groups total.

words (comma-separated, equal length)

def num_special_equiv_groups(words):
    seen = set()
    for w in words:
        evens = sorted(w[0::2])
        odds = sorted(w[1::2])
        sig = "".join(evens) + "|" + "".join(odds)
        seen.add(sig)
    return len(seen)

function numSpecialEquivGroups(words) {
  const seen = new Set();
  for (const w of words) {
    const evens = [], odds = [];
    for (let i = 0; i < w.length; i++) {
      (i % 2 === 0 ? evens : odds).push(w[i]);
    }
    const sig = evens.sort().join("") + "|" + odds.sort().join("");
    seen.add(sig);
  }
  return seen.size;
}

class Solution {
    public int numSpecialEquivGroups(String[] words) {
        Set<String> seen = new HashSet<>();
        for (String w : words) {
            char[] evens = new char[(w.length() + 1) / 2];
            char[] odds = new char[w.length() / 2];
            for (int i = 0; i < w.length(); i++) {
                if (i % 2 == 0) evens[i / 2] = w.charAt(i);
                else odds[i / 2] = w.charAt(i);
            }
            Arrays.sort(evens);
            Arrays.sort(odds);
            seen.add(new String(evens) + "|" + new String(odds));
        }
        return seen.size();
    }
}

int numSpecialEquivGroups(vector<string>& words) {
    unordered_set<string> seen;
    for (auto& w : words) {
        string evens, odds;
        for (int i = 0; i < (int)w.size(); i++) {
            (i % 2 == 0 ? evens : odds).push_back(w[i]);
        }
        sort(evens.begin(), evens.end());
        sort(odds.begin(), odds.end());
        seen.insert(evens + "|" + odds);
    }
    return (int)seen.size();
}

Explanation

You can only swap characters that sit at even positions among themselves, and odd positions among themselves. So the actual order within each group does not matter — only which letters live at even spots and which live at odd spots.

That gives a clean canonical signature: split the word into its even-indexed and odd-indexed characters, sort each half, and join them as sortedEvens + "|" + sortedOdds. Two words are special-equivalent exactly when these signatures match.

We drop every signature into a hash set. Since a set ignores duplicates, its final size is the number of distinct groups.

Example: "abcd" has evens a,c → ac and odds b,d → bd, signature ac|bd. "cdab" has evens c,a → ac and odds d,b → bd, the same ac|bd, so they share a group.

After processing all words, len(seen) is the answer.

Time: O(n · k log k) Space: O(n · k)