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
Swapping means positions are irrelevant, so only the frequency profile matters. Transforming means the labels attached to those frequencies can be permuted — but only among characters that already exist. So two conditions decide it: the same set of characters, and the same multiset of counts.
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).
What each operation actually preserves
Operation 1 rearranges characters, so it changes nothing about which characters appear or how often — it only destroys positional information. Operation 2 swaps two characters wholesale, exchanging their counts, but it cannot introduce a character that was absent or remove one entirely: a character with count 5 becomes a different label with count 5. So the character set is invariant, and the multiset of counts is invariant, while the pairing between them is free.
The two conditions, and why both are needed
Condition one: set(word1) == set(word2). Without it, "a" and "b" would pass — both have a single character appearing once — but no operation can turn an a into a b when there is no b to swap with. Condition two: the sorted lists of counts must match. Without it, "aabb" and "aaab" would pass the set test but their profiles are [2,2] versus [3,1], and no permutation of labels can reshape that.
Implementation and cost
Count both strings, compare the key sets directly, then sort both count lists and compare. Sorting at most 26 values is effectively constant, so the total is O(n + m) dominated by the counting pass, with O(1) space since the alphabet is bounded. A quick length check first is a free early exit: strings of different lengths can never be close, because both operations preserve total length.
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.