Determine if Two Strings Are Close

Problem

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

1. Swap any two characters of the string (e.g. abcde → aecdb).
2. 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 infeasible at this size. The solution comes from identifying what the operations preserve.

Think about it first

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


def closeStrings(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 up to 10^5 characters; this approach fails even on inputs of length 12. The operations must be analyzed, not simulated.

Approach 2 — Invariants (Counter + sorted frequencies)

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


def closeStrings(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":

1. c1 = {a: 2, b: 3, c: 1}, c2 = {a: 1, b: 2, c: 3}.
2. Key sets: {a, b, c} vs {a, b, c} — equal.
3. 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

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.”

def closeStrings(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 gives you transformation operations, 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 answer. Frequency signatures are the usual carrier of those invariants for string problems.