Get started

Similar String Groups — Hard Problem & Solution

Two strings X and Y are similar if they are equal, or if swapping the letters at two positions of X turns it into Y.

Problem statement

Two strings X and Y are similar if they are equal, or if swapping the letters at two positions of X turns it into Y. For example, "kairo" and "akiro" are similar (swap positions 0 and 1), while "kairo" and "rokai" are not.

Similarity links strings into groups: a string belongs to a group if it is similar to at least one other string in that group, so two strings can share a group without being similar to each other directly.

You are given strs, where every string is an anagram of every other. Return the number of groups.

Example 1

Input: strs = ["kairo","akiro","akior","rokai"]
Output: 2
Explanation: `kairo`–`akiro`–`akior` chain together; `rokai` is similar to none of them.

Example 2

Input: strs = ["abc","abc"]
Output: 1
Explanation: Equal strings are similar.

Example 3

Input: strs = ["abcd","badc","dcba"]
Output: 3

Constraints

  • 1 <= strs.length <= 300
  • 1 <= strs[i].length <= 300
  • strs[i] consists of lowercase letters only
  • all words in strs have the same length and are anagrams of each other

How to solve Similar String Groups

Groups are connected components of the similarity graph. For anagrams, similarity is just 'differ in zero or exactly two positions', so a pairwise scan with union-find counts the components.

Approach

  1. Start with n singleton sets and a group count of n.
  2. For every pair (i, j) in different sets, count mismatched positions, bailing out after the third.
  3. If the count is 0 or 2, union the pair and decrease the group count.
  4. Return the group count.

Why it works

If two anagrams differ in exactly two positions p and q, the multisets force X[p] = Y[q] and X[q] = Y[p], so swapping p and q in X gives Y; one mismatch is impossible for anagrams, and three or more cannot be fixed by one swap. Union-find then merges exactly the similar pairs, and connected components are the groups by definition.

Complexity

  • Time — O(n² · L)
  • Space — O(n)

Pitfalls

  • Groups are transitive closures — two strings in one group need not be similar to each other.
  • Identical strings count as similar.
  • Skip pairs already in the same set to save the comparison.

Reference solution

Python

from typing import List

def numSimilarGroups(strs: List[str]) -> int:
    n = len(strs)
    root = list(range(n))

    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def similar(a, b):
        diff = 0
        for x, y in zip(a, b):
            if x != y:
                diff += 1
                if diff > 2:
                    return False
        return diff != 1

    groups = n
    for i in range(n):
        for j in range(i + 1, n):
            ra, rb = find(i), find(j)
            if ra != rb and similar(strs[i], strs[j]):
                root[ra] = rb
                groups -= 1
    return groups

JavaScript

var numSimilarGroups = function(strs) {
    var n = strs.length;
    var root = [];
    for (var i = 0; i < n; i++) root.push(i);
    var find = function(x) {
        while (root[x] !== x) { root[x] = root[root[x]]; x = root[x]; }
        return x;
    };
    var similar = function(a, b) {
        var diff = 0;
        for (var k = 0; k < a.length; k++) {
            if (a.charCodeAt(k) !== b.charCodeAt(k) && ++diff > 2) return false;
        }
        return diff !== 1;
    };
    var groups = n;
    for (var p = 0; p < n; p++) {
        for (var q = p + 1; q < n; q++) {
            var rp = find(p), rq = find(q);
            if (rp !== rq && similar(strs[p], strs[q])) { root[rp] = rq; groups--; }
        }
    }
    return groups;
};

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

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings