839. Similar String Groups
On LeetCode ->Problem¶
Given equal-length strings that are all anagrams, connect two strings when they are identical or one swap makes them equal. Return the number of connected components.
Key trick¶
Two anagrams are directly similar exactly when they differ at zero or two positions; use DSU to merge directly similar pairs and capture transitive similarity.
Trap¶
- Similarity itself is not transitive, but group membership is.
- When merging DSU nodes, merge their roots returned by
find, not their immediate parents. - Two mismatches must cross-match after swapping unless relying on the anagram guarantee.
Why is it interesting?¶
It combines a local string comparison with graph connectivity: strings that are not directly similar can still belong to the same component.
Python solution¶
class Solution:
def numSimilarGroups(self, strs: list[str]) -> int:
n = len(strs)
parent = list(range(n))
size = [1] * n
def find(x):
# Path compression keeps future operations nearly constant-time.
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
root_a = find(a)
root_b = find(b)
if root_a != root_b:
# Union by size prevents unnecessarily deep trees.
if size[root_a] < size[root_b]:
root_a, root_b = root_b, root_a
parent[root_b] = root_a
size[root_a] += size[root_b]
def similar(s, t):
# Works because s and t are anagrams
diff = 0
for a, b in zip(s, t):
if a != b:
diff += 1
if diff > 2:
return False
return diff in (0, 2)
for i in range(n):
for j in range(i + 1, n):
if similar(strs[i], strs[j]):
union(i, j)
return sum(find(i) == i for i in range(n))
Time: \(O(n^2k)\), where \(n\) is the number of strings and \(k\) is their length.
Space: \(O(n)\) auxiliary space.
Comment on my solution¶
The graph model and swap generation are valid, but union does not find the actual roots:
These values may only be immediate parents. Reassigning one can detach it from its existing component, producing too many groups. The correctness fix is:
Generating every swap also costs \(O(nk^3)\) because there are \(O(k^2)\) swaps and each sliced string takes \(O(k)\) to construct. Comparing each pair directly reduces this to \(O(n^2k)\).
# Wrong Answer: 73/77 testcases passed
# ["zkhnmefhyr","ykznfhehmr","mkhnyefrzh","zkhnyefrmh","zkmnhefhyr","ykznhfehmr","zkynhfehmr","mkhnhefrzy","zkhnmefryh","zkmnhfehyr"]
# Output: 2
# Expected: 1
class Solution:
def numSimilarGroups(self, strs: list[str]) -> int:
strs_set = set(strs)
parent = {s:s for s in strs}
def find(s):
if parent[s] != s:
parent[s] = find(parent[s])
return parent[s]
def union(s1, s2):
root_1 = parent[s1]
root_2 = parent[s2]
if root_1 != root_2:
if root_1 < root_2:
parent[root_2] = root_1
else:
parent[root_1] = root_2
for s in strs:
for i in range(len(s)):
for j in range(i + 1, len(s)):
# swap s[i] and s[j]
t = s[:i] + s[j] + s[i+1:j] + s[i] + s[j+1:]
if t in strs_set:
union(s,t)
for s in strs:
find(s)
return len({parent[s] for s in strs})
Extra¶
Why union by size prevents unnecessarily deep trees?¶
I don't get what the
sizearray is keeping track off and why do we need it. Specifically, this is unclear to me:
size[root] tracks how many strings belong to that root's component. Initially, each string is alone, so every size is 1.
Only sizes stored at current roots matter. Sizes at non-root nodes can become outdated and are ignored.
What this code does¶
# Make root_a the root of the larger component.
if size[root_a] < size[root_b]:
root_a, root_b = root_b, root_a
# Attach the smaller component beneath the larger one.
parent[root_b] = root_a
# Record the combined component size.
size[root_a] += size[root_b]
Suppose the components look like this:
After merging:
Only nodes in the smaller component become one level deeper.
Why attach the smaller component?¶
Attaching large components beneath small ones repeatedly can create a long chain. Finding its root would require traversing many parents.
By attaching the smaller component beneath the larger one, whenever a node becomes deeper, its component's size at least doubles. That limits its depth to \(O(\log n)\) even without path compression.
Do we need size?¶
Not for correctness. You could always attach root_b beneath root_a, provided both are actual roots.
size is a performance optimization. Together with path compression, it makes DSU operations effectively constant-time in practice.
More about the size¶
Ok.
- But swapping roots doesn't change the size
- And as we are calling
findonaandb, ancestors ofaandbare "compressed" and we have no information about the shape of their subtree which can already compressed. The size (which is counting nodes) doesn't seem to account for the tree shape. What am I missing?
You're right on both points. The missing distinction is component size versus tree shape.
Swapping roots does not change sizes¶
It only changes which root the local names refer to:
Before:
root_a = A, size[A] = 2
root_b = B, size[B] = 5
After swapping:
root_a = B, size[B] = 5
root_b = A, size[A] = 2
Neither component changes. The swap ensures the subsequent assignment attaches the smaller component under the larger one.
Size does not describe tree shape¶
Correct: size[root] counts component members, not height or depth. Path compression changes the shape but does not change membership, so sizes remain valid.
Also, find(a) compresses only the path from a to its root, not the entire component.
Why size is still useful¶
Union by size does not necessarily choose the merge producing the shallowest tree. It gives a different guarantee:
Whenever a node's depth increases because of a union, the size of its component at least doubles.
If a smaller component has size \(s\) and the larger has size \(t \ge s\), attaching the smaller beneath the larger gives:
A node can therefore experience at most \(O(\log n)\) such depth increases. Path compression only reduces depth, so it cannot invalidate this bound.
Size is not a measurement of tree shape; it is a way to control how often nodes can become deeper, regardless of the current shape.
Link between component size increase and the \(O(\log n)\) depth increases¶
What is the link between "Whenever a node's depth increases because of a union, the size of its component at least doubles." and this "A node can therefore experience at most \(O(\log n)\) such depth increases.".
I'm missing something here about the intrinsinct nature of binary tree. Can you expand a bit?
It's not about binary trees: DSU trees can have any number of children. The logarithm comes from repeated doubling.
Pick one node and track its component size each time a union increases its depth:
After \(k\) such increases, its component must contain at least \(2^k\) nodes.
But there are only \(n\) nodes in total, so:
Taking the base-2 logarithm gives:
For example, with \(n = 16\), a node can experience at most four depth increases caused by unions. A fifth would require a component containing at least \(32\) nodes, which is impossible.
The sizes need not exactly double; they may grow faster. That only makes the number of possible depth increases smaller.
The connection is: exponential growth in component size limits the number of growth events to a logarithm. Path compression can decrease depth, but it never shrinks the component, so this argument still holds.