Determine if Two Strings Are Close

Solving tips

Don't simulate the operations; characterize their invariants (what they cannot change).
Swaps make order irrelevant and transforms shuffle which letter owns which count, so two strings are close iff they share the same letter SET and the same sorted multiset of frequencies.
Both conditions are required: sorted frequencies alone fails 'aab' vs 'bbc'; matching letter sets alone fails 'a' vs 'aa'.
Use Counter or a fixed 26-int array; target O(n) time and O(1) space (26-letter alphabet).

Problem

Two strings are close if you can turn one into the other using any sequence of these two operations:

Swap any two characters of the string (e.g. abcde → aecdb).
Transform one existing character into another existing character, applying it to every occurrence of both simultaneously (e.g. aacabb → bbcbaa: every a becomes b and every b becomes a).

Given word1 and word2, return True if they are close, False otherwise.

Examples

word1 = "abc", word2 = "bca" → True — operation 1 alone can produce any rearrangement.
word1 = "a", word2 = "aa" → False — no operation changes the length.
word1 = "cabbba", word2 = "abbccc" → True — cabbba has a×2, b×3, c×1 and abbccc has a×1, b×2, c×3: same character set {a, b, c}, same sorted frequencies [1, 2, 3], so transforms plus swaps can bridge them.

Constraints

1 <= word1.length, word2.length <= 10^5
Lowercase English letters only.

Searching over operation sequences is hopeless at this size — you need to find what the operations preserve.

Think about it first

Hint 1

Operation 1 means character order never matters. What single object fully describes a string once order is irrelevant?

Hint 2

Operation 2 exchanges the frequency counts of two characters that are both present — it can shuffle *which letter owns which count*, but what two things can it never change?

Hint 3

Two strings are close iff (a) they use exactly the same *set* of letters, and (b) their sorted lists of letter frequencies are identical. Compare `set(word)` and `sorted(Counter(word).values())` for both.

TL;DR

Compare invariants — same character set and same sorted frequency multiset — O(n) time, O(1) space (26-letter alphabet).

Approach 1 — Brute force

Search the space of reachable strings directly: breadth-first search (BFS — explore all states one operation away, then two away, and so on) applying every possible swap and every possible transform.

from collections import deque


class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        if len(word1) != len(word2):
            return False
        seen = {word1}
        queue = deque([word1])
        while queue:
            cur = queue.popleft()
            if cur == word2:
                return True
            chars = list(cur)
            n = len(chars)
            for i in range(n):                      # op 1: swap two positions
                for j in range(i + 1, n):
                    chars[i], chars[j] = chars[j], chars[i]
                    nxt = "".join(chars)
                    chars[i], chars[j] = chars[j], chars[i]
                    if nxt not in seen:
                        seen.add(nxt)
                        queue.append(nxt)
            present = sorted(set(cur))
            for a in present:                       # op 2: transform a <-> b
                for b in present:
                    if a < b:
                        nxt = cur.translate(str.maketrans(a + b, b + a))
                        if nxt not in seen:
                            seen.add(nxt)
                            queue.append(nxt)
        return False

Complexity: the reachable set contains every permutation under every letter-relabeling — factorial in n — so time and space are exponential.

Strings can be 10^5 characters long; this dies on inputs of length 12. The operations must be understood, not simulated.

Approach 2 — Invariants (Counter + sorted frequencies)

The insight: ask what each operation can and cannot change.

Swaps generate every permutation, so order carries no information — only the frequency map matters.
A transform exchanges the counts of two letters that both occur, so it can shuffle which letter owns which count — but it can never introduce a new letter, delete one, or change the multiset of count values.

So two strings are close iff they use exactly the same set of letters and their frequency values, as a sorted list, are identical. Both conditions are also sufficient: sort the counts into place with transforms, then permute with swaps.

from collections import Counter


class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        c1, c2 = Counter(word1), Counter(word2)
        return set(c1) == set(c2) and sorted(c1.values()) == sorted(c2.values())

Walkthrough on word1 = "cabbba", word2 = "abbccc":

c1 = {a: 2, b: 3, c: 1}, c2 = {a: 1, b: 2, c: 3}.
Key sets: {a, b, c} vs {a, b, c} — equal.
Sorted values: [1, 2, 3] vs [1, 2, 3] — equal → True. (Concretely: transform a↔c to get counts a:1, b:3, c:2, transform b↔c to get a:1, b:2, c:3, then swaps arrange the order.)

And on word1 = "a", word2 = "aa": sorted values [1] vs [2] differ → False.

Complexity: O(n + k log k) time with k ≤ 26 distinct letters — effectively O(n); O(k) = O(1) space.

Approach 3 — Fixed 26-slot arrays

The insight: with a lowercase-only alphabet you don’t need hashing at all — two arrays of 26 counts capture everything, and “same key set” becomes “zero in one array exactly where it’s zero in the other.”

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        f1, f2 = [0] * 26, [0] * 26
        base = ord("a")
        for ch in word1:
            f1[ord(ch) - base] += 1
        for ch in word2:
            f2[ord(ch) - base] += 1
        for a, b in zip(f1, f2):
            if (a == 0) != (b == 0):    # a letter present in only one word
                return False
        return sorted(f1) == sorted(f2)

Walkthrough on word1 = "abc", word2 = "bca": both arrays have 1s at slots a, b, c and 0s elsewhere; the zero-pattern check passes and the sorted arrays are identical → True.

Complexity: O(n) time, O(1) space — sorting a constant-size 26 array is constant work.

Common pitfalls

Checking only that sorted frequency lists match: "aab" (a:2, b:1) vs "bbc" (b:2, c:1) have identical sorted counts [1, 2] but different letters — transforms only work between letters both present, so this must be False.
Checking only that letter sets match: "a" vs "aa", or "aabb" vs "aaab" — same letters, different count multisets.
Comparing c1 == c2 (full Counter equality) — too strict; that’s anagram equality, and it wrongly rejects "cabbba" vs "abbccc".
Forgetting an early length check is not needed as a separate step — unequal lengths already fail the sorted-frequency comparison — but adding one is a harmless fast path.

Pattern takeaway

When a problem hands you transformation operations, don’t simulate them — characterize their invariants: the quantities no operation can change. If two objects agree on all invariants and the operations are rich enough to realize any configuration sharing them, equality of invariants is the whole answer. Hash-map frequency signatures are the usual carrier of those invariants for string problems.