Determine if Two Strings Are Close
Determine if Two Strings Are Close: two strings are close if one can become the other using any number of two operations — swapping any two existing characters, or transforming every occurrence of one character into another and vice versa.
- 1 <= word1.length, word2.length <= 10⁵
- word1 and word2 contain only lowercase English letters.
Intuition
Determine if two strings are close asks whether one string can be turned into the other using two operations: swapping any two existing characters, and swapping every occurrence of one character with every occurrence of another.
Both operations are deceptively powerful, and reasoning about sequences of them is hopeless. The productive move is to ask what each operation cannot change — the invariants:
- The first operation rearranges positions freely, so order never matters; the second permutes which letter carries which count, so the multiset of frequencies never changes but their labels do.
That gives exactly two conditions to check, and nothing else.
First, both strings must use the same set of distinct characters. The second operation swaps existing letters, so it can never introduce a letter that was absent or eliminate one entirely. If a appears in one string and not the other, no sequence of operations closes that gap.
Second, the sorted lists of frequency counts must match. The counts themselves are preserved as a collection, but which character owns each count is freely reassignable — so compare the sorted counts, not the per-character counts.
Getting one condition without the other fails: "aab" and "bbc" have matching sorted counts [1, 2] but different character sets, so the answer is false.
A length check is implied by the frequency comparison, but testing it first is a cheap early exit.
To determine if two strings are close, note that when operations are given as rewrite rules, the solution is usually an invariant — the property no operation can alter. Identify what is preserved and compare only that. Here it is the character set and the count multiset; the same reasoning solves Buddy Strings and most 'can X become Y' questions.
Approach
Before reading on: work out exactly what each of the two operations can and cannot change. Then decide why "a" and "b" are not close even though both have one character appearing once. Aim for O(n + m).
Reason about invariants, not sequences
Tracing sequences of operations is hopeless. Ask instead what the operations cannot change — those invariants become the exact conditions to test.
Note that order never matters
The first operation rearranges characters freely, so position carries no information. Only the character counts survive it.
Compare the distinct character sets
The second operation swaps existing letters, so it can never introduce or remove one. If a letter appears in one string and not the other, the answer is false.
Compare the sorted frequency counts
Transforming letters permutes which character owns which count, but preserves the collection. Sort both count lists and compare — never compare per-character counts.
Require both conditions
"aab" and "bbc" share sorted counts [1, 2] but differ in character sets, so they are not close. Either condition alone is insufficient.
Exit early on length
Different lengths cannot have matching frequency multisets. Checking length first is a cheap rejection before any counting.
Cost of the checks
Counting is linear and sorting at most 26 counts is constant, giving O(n log n) time — effectively O(n) — and O(1) space for the fixed alphabet.
Solution & live demo
Common pitfalls
Comparing the counters directly
return counts1 == counts2
return sorted(counts1.values()) == sorted(counts2.values())
That tests for anagrams, which is stricter than closeness. "cabbba" and "abbccc" are close — the counts can be permuted between characters — but their counters are not equal.
Skipping the character-set check
return sorted(counts1.values()) == sorted(counts2.values())
if set(counts1) != set(counts2):
return False
# then compare the profilesOperation 2 can only exchange characters that both exist. Without the set check, "a" and "b" both give the profile [1] and are wrongly reported close.
Comparing counts without sorting
return list(counts1.values()) == list(counts2.values())
return sorted(counts1.values()) == sorted(counts2.values())
Dictionary ordering follows insertion, so the same multiset in a different order compares unequal. The pairing between character and count is exactly what operation 2 is free to permute, so only the sorted multiset is meaningful.
Edge cases
Both operations preserve length, so the count multisets cannot match and the answer is false.
Sets match but count profiles [2,2] and [3,1] differ, so false.
Count profiles match but the character sets differ, so false.
Both conditions hold trivially and the answer is true.
Sets match and profiles are permutations of each other, so true.