LeetCode 1657: Two Strings Are Close | Interactive Dry Run & Logic

On this page

Problem statement
Approach 1 — Brute force (nested frequency matching)
Approach 2 — Better (sort and compare)
Approach 3 — Optimal (fixed-array counting)
Interview notes
FAQ

Problem Statement

Two strings are "close" if one can be turned into the other using any number of two operations: swapping any two existing characters, or transforming every occurrence of one existing character into another existing character (and vice versa). Return whether word1 and word2 are close.

Example: word1 = "cabbba", word2 = "abbccc" → true. word1 has frequencies {c:1, a:2, b:3} and word2 has {a:1, b:2, c:3} — different characters have different counts, but the same set of counts, {1, 2, 3}, appears in both.

We'll trace all three approaches on this exact pair, watching each one confirm true — and later revisit a trickier pair, "aaa" and "bbb", to see why matching frequencies alone isn't the whole story.

Approach 1 · Brute Force

Count Frequencies, Then Match Them One at a Time

Intuition

Two strings can be reshaped into each other exactly when they use the same set of characters and the same "shape" of frequencies — which character has which count doesn't matter, only that the counts line up somehow. The most direct way to check that: build a frequency map for each string, confirm they use the same characters, then try to match each frequency in word1's map to an unused, equal frequency in word2's map by searching for it.

Algorithm

If the lengths differ, return false immediately.
Build frequency maps for both strings using a hash map.
Check that both maps use exactly the same set of characters.
For each frequency value in word1's map, search through word2's frequency values for a matching, not-yet-used value, and remove it once found.
If every frequency finds a match, return true; if any search fails, return false.

C++ Code

bool closeStrings(string word1, string word2) {
    if (word1.size() != word2.size()) return false;

    unordered_map<char, int> freq1, freq2;
    for (char c : word1) freq1[c]++;
    for (char c : word2) freq2[c]++;

    for (auto& [ch, cnt] : freq1) if (!freq2.count(ch)) return false;
    for (auto& [ch, cnt] : freq2) if (!freq1.count(ch)) return false;

    vector<int> vals2;
    for (auto& [ch, cnt] : freq2) vals2.push_back(cnt);

    for (auto& [ch, cnt] : freq1) {
        bool matched = false;
        for (int i = 0; i < (int)vals2.size(); i++) {
            if (vals2[i] == cnt) {
                vals2.erase(vals2.begin() + i);
                matched = true;
                break;
            }
        }
        if (!matched) return false;
    }
    return true;
}

Dry Run

Complexity Analysis

Metric	Value	Why
Time	O(n + m²)	n to build the maps, m² for the nested search-and-remove over the alphabet (m ≤ 26)
Space	O(m)	two hash maps plus a temporary values list, all bounded by the alphabet size
Practical issue	Doesn't scale with alphabet size	the nested search becomes the bottleneck if the character set were much larger than 26

Approach 2 · Better

Sort Both Frequency Lists, Then Compare

Intuition

Instead of searching for each frequency's match one at a time, sort both lists of frequencies first. Once sorted, "do these two lists contain the same multiset of values" becomes a simple element-by-element comparison — no searching, no removing, and no risk of accidentally mismatching an earlier value with the wrong later one.

Algorithm

Same setup as before: check lengths, build both frequency maps, and confirm the character sets match.
Collect each map's frequency values into a list.
Sort both lists.
Compare the sorted lists directly for equality.

C++ Code

bool closeStrings(string word1, string word2) {
    if (word1.size() != word2.size()) return false;

    unordered_map<char, int> freq1, freq2;
    for (char c : word1) freq1[c]++;
    for (char c : word2) freq2[c]++;

    for (auto& [ch, cnt] : freq1) if (!freq2.count(ch)) return false;
    for (auto& [ch, cnt] : freq2) if (!freq1.count(ch)) return false;

    vector<int> counts1, counts2;
    for (auto& [ch, cnt] : freq1) counts1.push_back(cnt);
    for (auto& [ch, cnt] : freq2) counts2.push_back(cnt);

    sort(counts1.begin(), counts1.end());
    sort(counts2.begin(), counts2.end());

    return counts1 == counts2;
}

Dry Run

Complexity analysis

Metric	Value	Why
Time	O(n + m log m)	n to build the maps, m log m to sort the frequency lists (m ≤ 26)
Space	O(m)	two hash maps plus two small frequency lists
Improvement	No nested search	sorting resolves the whole matching problem in one predictable step

Approach 3 · Optimal

Fixed-Size Arrays Instead of Hash Maps

Intuition

The alphabet here is fixed at 26 lowercase letters — there's no need to pay for hash map overhead (hashing, bucket allocation, iteration order) just to count them. A plain 26-length array indexed by c - 'a' counts frequencies just as well, in a single tight pass, with no hashing at all. The character-set check becomes a simple "is this slot non-zero in both arrays" comparison, and the frequency check is the same sort-and-compare as before, just on arrays instead of vectors pulled out of maps.

Algorithm

If the lengths differ, return false.
Count each string's characters into a fixed array<int, 26>.
For each of the 26 letters, check that it's present in both strings or absent from both — a mismatch means the character sets differ.
Sort both 26-length arrays and compare them directly for equality.

C++ Code

bool closeStrings(string word1, string word2) {
    if (word1.size() != word2.size()) return false;

    array<int, 26> freq1{}, freq2{};
    for (char c : word1) freq1[c - 'a']++;
    for (char c : word2) freq2[c - 'a']++;

    for (int i = 0; i < 26; i++) {
        if ((freq1[i] > 0) != (freq2[i] > 0)) return false;
    }

    sort(freq1.begin(), freq1.end());
    sort(freq2.begin(), freq2.end());

    return freq1 == freq2;
}

Dry Run

Complexity Analysis

Metric	Value	Why
Time	O(n)	counting is a single linear pass; sorting a fixed 26-length array is constant time
Space	O(1)	two fixed-size 26-length arrays — no hash maps, no dynamic vectors
Why optimal	No hashing overhead	direct array indexing replaces every hash map lookup from the earlier approach

Interview Notes

How to talk through it

State the two-part condition out loud before coding: same character set, and same multiset of frequencies. Naming both conditions up front shows you've fully reasoned about what each operation can and can't do.
Walk through why swap and transform map to these two conditions specifically — swap lets you reorder freely within a string (irrelevant to frequency shape), and transform lets you permute which character owns which frequency, but never introduces a character that wasn't already there.
Mention the O(n + m²) or O(n + m log m) versions briefly, then land on the fixed-array version, explicitly noting that the alphabet size being fixed at 26 is exactly what makes O(1) space possible.

The pitfall almost everyone hits

It's tempting to check only that the sorted frequency lists match. That's not enough: "aaa" and "bbb" both have frequency list [3], but they are not close. The transform operation can only relabel characters that already exist in the string — since "aaa" contains no 'b' at all, there's no valid transform to reach "bbb". This is exactly why the separate character-set check is required, not just a nice-to-have.

Common follow-ups

"Can you avoid sorting entirely?" → yes — build a "frequency of frequencies" count (how many letters appear exactly once, exactly twice, and so on) for each string and compare those two small distributions directly, which is a valid alternative optimal approach.
"What if the alphabet were much larger, like Unicode?" → the fixed-size array assumption breaks down; you'd fall back to a hash map for counting, but the same set-and-frequency-multiset logic still applies.
"Why check lengths first?" → it's a fast, free rejection: neither operation changes the total character count, so mismatched lengths can never be close.

Edge cases to mention

Different lengths (like "a" vs "aa") → immediately false, no further work needed.
Identical strings → trivially true.
Disjoint character sets with matching frequencies (like "aaa" vs "bbb") → false, per the pitfall above.

Frequently Asked Questions

What makes two strings close according to this problem?

They must use exactly the same set of distinct characters, and the multiset of frequencies — which counts appear, regardless of which character has which count — must match between them.

Which approach should I lead with in an interview?

State the two-part condition first, then write the sort-and-compare version directly — it's clean and easy to verify correct — and mention the fixed-array optimization as a natural follow-up once the alphabet size is established as small and fixed.

Why isn't matching frequency multisets alone enough?

Because relabeling can only reassign frequencies among characters that already exist in the string — it can never introduce a character that wasn't there. Two strings with completely different character sets can still have matching frequency lists, like "aaa" and "bbb", yet never be close.

What is the time and space complexity of the optimal solution?

The fixed-array approach runs in O(n) time for the single counting pass, with sorting and comparing the 26-length arrays taking constant time, and uses O(1) extra space overall.

Problem Statement

Count Frequencies, Then Match Them One at a Time

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Sort Both Frequency Lists, Then Compare

Intuition

Algorithm

C++ Code

Dry Run

Complexity analysis

Fixed-Size Arrays Instead of Hash Maps

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Interview Notes

How to talk through it

The pitfall almost everyone hits

Common follow-ups

Edge cases to mention

Related problems

Frequently Asked Questions

Chakradhar

Problem Statement

Count Frequencies, Then Match Them One at a Time

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Sort Both Frequency Lists, Then Compare

Intuition

Algorithm

C++ Code

Dry Run

Complexity analysis

Fixed-Size Arrays Instead of Hash Maps

Intuition

Algorithm

C++ Code

Dry Run

Complexity Analysis

Interview Notes

How to talk through it

The pitfall almost everyone hits

Common follow-ups

Edge cases to mention

Related problems

Frequently Asked Questions