Abstract / Summary

Group strings that can be made similar by swapping exactly two characters in any string

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 56% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Depth First Search
• Hash Table
• String
• Union Find

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of counting similarity groups among a list of equal-length strings. Two strings belong to the same group when they can be transformed into each other by swapping at most one pair of characters, which translates to having at most two mismatched positions. The algorithm builds an undirected graph where each vertex represents a string and an edge connects two vertices whose strings differ in no more than two places. The number of connected components in this graph is the answer. A union-find (disjoint-set) data structure is used to merge vertices that are directly similar, and the final count of distinct set representatives yields the number of groups.

Key Steps

Initialization of the Disjoint-Set

size = len(strs)
parent = [i for i in range(size)]

A list parent holds the representative of each set. Initially each string is its own parent, establishing size singleton groups.

Find with Path Compression

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])   # path compression
    return parent[x]

The find routine climbs the parent chain until it reaches the root. While unwinding the recursion, it rewires each visited node directly to the root, flattening the tree and accelerating future lookups.

Union by Minimum Index

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

After locating the roots of the two sets, the function merges the higher-indexed root into the lower-indexed one. This deterministic rule keeps the tree shallow without requiring an explicit rank array.

Pairwise Similarity Check

for i in range(size):
    for j in range(i + 1, size):
        a = strs[i]
        b = strs[j]

        count = 0
        for k in range(len(a)):
            if a[k] != b[k]:
                count += 1

        if count <= 2:
            union(i, j)

The double loop enumerates every unordered pair of strings. For each pair, a character-by-character comparison tallies mismatches. When the mismatch count does not exceed two, the corresponding indices are united, indicating that the two strings belong to the same similarity group.

Final Group Count

groups = set()
for i in range(len(parent)):
    groups.add(find(i))
return len(groups)

A set collects the distinct root identifiers after applying find to each index. The cardinality of this set is the number of similarity groups.

Edge Cases Handled

When the input list is empty, size becomes zero, the outer loops are skipped, and the final set remains empty, resulting in a return value of zero groups.

If the list contains a single string, the initialization creates one parent entry, the nested loops never execute, and the final set contains the sole root, yielding one group.

Identical strings produce a mismatch count of zero, satisfying the count <= 2 condition, so they are merged into the same set, correctly treating duplicates as a single group.

Strings that differ in exactly two positions are also merged, reflecting the allowed single swap transformation.

Because the inner character loop iterates over the length of the first string, the code implicitly assumes all strings share the same length; when this holds, the comparison correctly accounts for every position.

Performance Optimizations

The union-find structure incorporates path compression in find, which dramatically reduces the depth of the parent tree after each lookup, leading to near-constant amortized cost for subsequent operations.

The union step chooses the smaller index as the new root, providing a simple heuristic that avoids creating long chains and contributes to a flatter tree shape.

The double loop only examines each unordered pair once (j starts at i + 1), eliminating redundant comparisons and halving the number of pairwise checks compared to a naïve double iteration over all indices.

The mismatch counting stops only after scanning the entire string, but because the condition count <= 2 is evaluated after the full scan, the algorithm avoids premature termination that could miss later mismatches, ensuring correctness while keeping the inner loop straightforward and cache-friendly.

Collecting distinct roots via a set after all unions leverages the fast hash-based insertion of Python’s built-in set type, providing an efficient way to deduplicate representatives without additional traversal structures.

Imagine you have a big treasure chest full of word cards. Some of these words look almost the same, only changing two little letters. This code starts by giving every word its own special spot. Then, it looks at every pair of words to see if they are close enough to be friends. If two words are similar, the code puts them together in the same friend group. Think of it like inviting kids to play in groups on a playground. If a word is friends with someone, they all join up. Once all the words have checked to see who they match with, the code counts how many different play groups were made. It is like looking at the playground and counting how many scattered groups of friends are hanging out together.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python			TS
	WalkCCC	C++		Java
	leetcode.ca	C++		Java		Python	Go		TS
	LeetcodeHelp	C++		Java		Python
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	halfrost						Go
	JoshCrozier		JS
	lkwq007					Python
	ruoru				Rust
	suxrobGM							C#
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality