637. Determine if Two Strings Are Close
Two strings are close if one can be turned into the other by any sequence of these two moves:
- Rearrange — swap any two characters. Applied repeatedly, this reaches every possible reordering of the string.
- Relabel — pick two distinct characters that both occur in the string and exchange them everywhere: every copy of the first becomes the second and every copy of the second becomes the first (e.g.
aacabbwith a↔b becomesbbcbaa).
Given two strings word1 and word2 consisting of lowercase English letters, return whether they are close.
Your function receives the two strings and returns a boolean. The judge prints exactly true or false (lowercase).
Example 1:
Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: Rearranging alone is enough: abc → acb → bca uses only character swaps.
Example 2:
Input: word1 = "a", word2 = "aa"
Output: false
Explanation: Neither move ever changes a string's length, so a 1-character string can never become a 2-character one.
Example 3:
Input: word1 = "cabbba", word2 = "abbccc"
Output: true
Explanation: cabbba has counts a:2, b:3, c:1 and abbccc has a:1, b:2, c:3. Relabeling can hand the count 3 from b to c and shuffle the rest, then rearranging fixes the order.
Constraints:
- 1 ≤ word1.length, word2.length ≤ 10⁵
- word1 and word2 contain only lowercase English letters.
Hints:
Neither move creates or destroys characters, so think in terms of what each move CANNOT change. Rearranging preserves the multiset of letters; relabeling preserves the multiset of counts. What stays invariant across any sequence of both?
Two invariants survive everything: (1) the SET of distinct letters that appear (relabeling only exchanges two letters that both already occur, so it never introduces or removes a letter), and (2) the multiset of frequency values (relabeling just reassigns which letter owns which count).
So the check is: same distinct-letter set AND the sorted lists of nonzero frequencies are identical. Both conditions are also sufficient — sorting the 26 counts, or bucketing count-of-counts, decides it in O(n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: word1 = "abc", word2 = "bca"
Expected output: true