Groups of Special-Equivalent Strings

Medium
1177.

Groups of Special-Equivalent Strings

Groups of Special-Equivalent Strings is a medium coding problem on arrays, strings and hash table, asked in Amazon and Meta interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {number}
 */
var numSpecialEquivGroups = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Groups of Special-Equivalent Strings — Problem & Solution

Groups of Special-Equivalent Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Groups of Special-Equivalent Strings is a medium coding problem on arrays, strings and hash table, asked in Amazon and Meta interviews.

  • Difficulty: Medium
  • Topics: Arrays, Strings, Hash Table, Sorting
  • Asked at: Amazon, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Groups of Special-Equivalent Strings

  1. Hint 1

    Moves only shuffle the even positions among themselves and the odd positions among themselves.

  2. Hint 2

    Any rearrangement of the even positions is reachable by swaps, and so is any rearrangement of the odd ones.

  3. Hint 3

    So two strings are equivalent exactly when their even-index letters form the same multiset and their odd-index letters do too — build that as a key and count distinct keys.

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)

Java

public static int numSpecialEquivGroups(String[] words) {
    Set<String> seen = new HashSet<>();
    for (String w : words) {
        int[] cnt = new int[52];
        for (int i = 0; i < w.length(); i++) cnt[(i % 2) * 26 + (w.charAt(i) - 'a')]++;
        seen.add(Arrays.toString(cnt));
    }
    return seen.size();
}

C++

int numSpecialEquivGroups(vector<string>& words) {
    set<vector<int>> seen;
    for (const string& w : words) {
        vector<int> cnt(52, 0);
        for (int i = 0; i < (int)w.size(); i++) cnt[(i % 2) * 26 + (w[i] - 'a')]++;
        seen.insert(cnt);
    }
    return (int)seen.size();
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings