637/670

637. Determine if Two Strings Are Close

Medium

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. aacabb with a↔b becomes bbcbaa).

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