Similar String Groups

Similar String Groups is a union-find classic. Two words are "similar" if you can turn one into the other by swapping a single pair of letters (or they are already equal). The job is to count how many groups of similar words there are — and that is exactly what a disjoint-set / union-find structure was built to do.

The slow way first

You could grow groups by hand: start with the first word, scan for everything similar to it, then everything similar to those, and so on — a flood fill. That works but is fiddly to manage, because a later word can suddenly bridge two groups you thought were separate.

The question to ask: how do I keep merging sets and always know how many distinct sets remain? That is the textbook job of union-find — it merges two sets in near-constant time and keeps a live count.

The idea: union every similar pair, count the roots

Give each string its own set. Then look at every pair of strings. Count how many positions they differ in: if that count is 0 or 2, the two are similar (anagrams of the same length can only differ in an even number of spots, and 2 means a single swap). When they are similar, union their sets. After all pairs, the number of distinct roots is the answer.

The key insight: similarity is transitive, so we never need to track groups directly. We just merge pairs, and union-find collapses the chains for us. The final group count is the number of roots left standing.

Walk through it

Step through the animation. Every string starts as its own group (count 4). tars and rats differ in 2 spots, so they merge (count 3). rats and arts merge next (count 2). arts and star differ in too many spots, so we skip. Finally tars and star are similar, pulling star into the big set (count 1). All four end up in one group.

Pseudocode

make a union-find with one set per string   # count starts at len(strs)
for each i:
    for each j after i:
        diff = number of positions where strs[i] and strs[j] differ
        if diff <= 2:
            union(i, j)                       # merge the two sets
return the union-find's set count            # = number of groups

The Python solution

def num_similar_groups(strs):
    uf = UnionFind(len(strs))
    for i in range(len(strs)):
        for j in range(i + 1, len(strs)):
            diff = sum(a != b for a, b in zip(strs[i], strs[j]))
            if diff <= 2:
                uf.union(i, j)
    return uf.count

• UnionFind(len(strs)) starts with every index as its own root, so count begins at the number of strings.
• The double loop walks every unordered pair (i, j) exactly once.
• sum(a != b for a, b in zip(...)) counts the positions where the two strings differ — the distance between them.
• diff <= 2 is the similarity test. Because the inputs are equal-length anagrams, a real swap differs in exactly 2 spots, and 0 means they are identical.
• uf.union(i, j) merges the two sets; a good UnionFind decrements count only when it actually joins two different roots.
• uf.count is the live number of groups once every pair has been considered.

Complexity

With n strings of length m, the pair comparisons dominate at O(n² · m). The union-find work is effectively linear in the number of unions thanks to path compression and union by rank, where alpha is the inverse-Ackermann function (basically a small constant).

When this pattern shows up

Practice