1657. Determine if Two Strings Are Close

Medium · solved 2026-10-01 · Open on LeetCode

hash-tablestringcounting

Time O(n + m) · Space O(1)

How to get there

Find what the operations can't change

1. Try the operations by hand. Swapping turns “abc” into “bca”: the letters move, their counts stay. Transforming every a into b and every b into a turns “aacabb” into “bbcbaa”: the letter a now has b’s old count and b has a’s. Searching through sequences of operations would never end, so look for what stays fixed instead.

2. List what neither operation changes.

Swapping changes only order, so order never matters; how often each letter appears does.
Transforming trades the counts of two letters that are already in the word. The set of letters stays the same, and so does the list of counts; only which letter holds which count changes.

3. Check that those are also enough. If two words use the same letters and the same counts, ignoring which letter has which, the transformation can hand each count to the right letter, and swaps then put the letters in order. So close means exactly: same letters, same count pattern. Equal length follows, which makes it a cheap first check.

4. Turn “same counts, ignoring letters” into something comparable. Count each letter, then count how many letters have each count. Two words have the same pattern exactly when those second maps are equal.

The reusable recipe: when operations can be applied any number of times, stop simulating them and find the invariants, the things no operation changes; then compare the invariants.

Let the variables' meanings write the loops

Variable	Always means
`d1`, `d2`	each letter of `word1`, `word2` mapped to how often it appears
`c1`, `c2`	each count mapped to how many letters of that word have it

Code	What it checks or builds
`if len(word1) != len(word2): return False`	the cheapest invariant first: equal counts need equal length
the two `for token in word` loops	`d1` and `d2`, one count per letter
the two `for token in d` loops	`c1` and `c2`, the count pattern of each word
`for token in d1: if token not in d2` and the reverse	the same set of letters, checked in both directions
`for count in c1:` and `for count in c2:`	the same count pattern: every count has the same number of letters on both sides
`return True`	every invariant matched

Every check returns False at its first mismatch, so a word that fails early skips the rest.

The method carries over: name the invariants first, give each one a variable, and the code becomes one loop to build each and one to compare each.

Alternatives compared

Approach	Time	Space	How it works
Count of counts (chosen)	O(n + m)	O(1)	Count each letter, then count how many letters have each count, and compare the maps key by key.
Sorted counts	O(n + m)	O(1)	Count each letter, then sort the at most 26 counts and compare the sorted lists.
`Counter`	O(n + m)	O(1)	`Counter(word)` for the letters, `Counter(counts.values())` for the counts, then two `==` comparisons.
`str.count` per letter	O(26 · (n + m))	O(1)	`word.count(ch)` for each of the 26 letters gives every count at once.

All four have the same bounds, since there are only 26 letters. They differ in how much of the counting runs in C instead of the Python interpreter: str.count scans in C, so 26 scans of each word beat one Python loop. On two 100,000-letter words, it ran about six times faster than the chosen code in a local timing.

solution.py

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        if len(word1) != len(word2):
            return False

        d1, d2 = {}, {} ## key: token, val: count
        c1, c2 = {}, {} ## key: count, val: occurrence

        for token in word1:
            if token not in d1:
                d1[token] = 1
            else:
                d1[token] += 1

        for token in word2:
            if token not in d2:
                d2[token] = 1
            else:
                d2[token] += 1

        for token in d1:
            if d1[token] not in c1:
                c1[d1[token]] = 1
            else:
                c1[d1[token]] += 1

        for token in d2:
            if d2[token] not in c2:
                c2[d2[token]] = 1
            else:
                c2[d2[token]] += 1

        for token in d1:
            if token not in d2:
                return False

        for token in d2:
            if token not in d1:
                return False

        for count in c1:
            if count not in c2:
                return False
            elif c1[count] != c2[count]:
                return False

        for count in c2:
            if count not in c1:
                return False
            elif c2[count] != c1[count]:
                return False

        return True

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.