Determine if Two Strings Are Close
Decide whether one string can become another by swapping characters and swapping two letters everywhere: compare lengths, letter sets and sorted letter counts.
Problem Understanding
Determine if Two Strings Are Close (LeetCode 1657): two strings are close if you can turn one into the other using, any number of times:
- Operation 1: swap any two existing characters, so
abcde→aecdb. - Operation 2: pick two letters that both occur and swap every occurrence of one with the other, so
aacabb→bbcbaa.
Given word1 and word2 of lowercase letters, return true if they are close.
Examples: "abc", "bca" → true; "a", "aa" → false; "cabbba", "abbccc" → true.
The Intuition: What the Operations Cannot Change
Instead of searching for a sequence of operations, ask what they leave untouched.
- The length. Neither operation adds or removes characters.
- The set of letters. Operation 2 only swaps letters that are already there, so a letter can never appear or disappear.
- The counts, as a multiset. Operation 1 keeps every count; operation 2 swaps two letters' counts. Sorted, the list of counts never changes.
And those three are enough: with equal sorted counts you can relabel letters to match the counts, then reorder. The counting is the same tally as Valid Anagram; anagrams are the special case where each letter keeps its own count.
Interactive Walkthrough
LENGTH · LETTERS · SORTED COUNTS
SAME LENGTH?
word1
0
1
2
3
4
5
word2
0
1
2
3
4
5
counts (letter:count)
Letters
0 / 0
Answer
:
Lengths: 6 and 6. Equal, so keep going
Next
word1[0] = 'c': count it, now 1
word1
word2
The figure counts both words into letter:count tiles, then runs the three checks in order. Try New letter and Counts differ to see each check fail on its own.
Dry Run Table
Input: word1 = "cabbba", word2 = "abbccc".
| Check | word1 | word2 | Result |
|---|---|---|---|
| Length | 6 | 6 | equal |
| Counts | a:2, b:3, c:1 | a:1, b:2, c:3 | |
| Letters | {a, b, c} | {a, b, c} | equal |
| Sorted counts | [1, 2, 3] | [1, 2, 3] | equal |
Answer: true. Swapping a and b everywhere, then b and c, lines the counts up, and operation 1 fixes the order.
The Solution Template
Three checks in order of cost. The Java, C++, JavaScript, TypeScript and C versions count into an array of 26; a letter is in a word exactly when its count is not 0.
Determine if Two Strings Are Close Code
1var closeStrings = function(word1, word2) {2 if (word1.length !== word2.length) {3 return false;4 }5 const c1 = new Array(26).fill(0), c2 = new Array(26).fill(0);6 for (const ch of word1) c1[ch.charCodeAt(0) - 97]++;7 for (const ch of word2) c2[ch.charCodeAt(0) - 97]++;8 for (let k = 0; k < 26; k++) {9 if ((c1[k] === 0) !== (c2[k] === 0)) {10 return false;11 }12 }13 c1.sort((a, b) => a - b);14 c2.sort((a, b) => a - b);15 return c1.every((v, k) => v === c2[k]);16};
Edge Cases & Common Mistakes
- Skipping the letter-set check:
"aab"and"aac"have equal sorted counts [1, 2] but are not close, because c never occurs in the first word. - Comparing counts per letter: that tests for anagrams, which is stricter;
"cabbba"and"abbccc"are close but not anagrams. - Different lengths: return false right away; the counts cannot match.
- Sorting the strings: sorting characters compares letters with their own counts, again the anagram test.
Summary
Two strings are close exactly when they have the same length, the same set of letters and the same sorted letter counts. Count both words and run the three checks: O(n) time, O(1) space for 26 letters.
More practice: DSA interview questions with answers · patterns cheat sheet