How do you solve Determine if Two Strings Are Close?

Count the frequency of each character in both strings using hash maps (Counters). Compare the sets of keys (unique characters) for equality. Then compare the sorted lists of frequency values. If both match, return true; otherwise, return false. This approach runs in O(n log n) due to sorting frequency lists, with n being the length of the strings.

What pattern does Determine if Two Strings Are Close use?

The Pattern: Hash Maps (Frequency Counting and Set Comparison) The Heuristic: When transformations allow character swaps and reassignments but preserve character sets and frequency multisets, reduce the problem to comparing these two properties using hash maps and sorted frequency arrays.

Determine if Two Strings Are Close | Hash Maps

Q: What is the time complexity of Determine if Two Strings Are Close?

O(n log n). Counting frequencies with hash maps is O(n). Sorting the frequency lists dominates with O(k log k), where k is the number of unique characters, which is at most 26 for lowercase English letters, effectively O(1) in practice but O(n log n) in general.

Problem

Given two strings word1 and word2, return true if they are close, or false otherwise. Two strings are close if you can transform one into the other using a series of operations: swapping any two existing characters or transforming every occurrence of one character into another existing character and vice versa.

1 ≤ word1.length, word2.length ≤ 10⁵
word1 and word2 contain only lowercase English letters

Example

Input: word1 = "abc", word2 = "bca"

Output: true

Starting with "abc", swapping 'a' and 'b' yields "bac", then swapping 'a' and 'c' yields "bca", which matches word2. The critical insight is that both strings have the same set of characters {'a','b','c'} and the same frequency distribution {1,1,1}, allowing transformation via the allowed operations.

Approach

Straightforward Solution

A brute-force approach might attempt to simulate all possible swaps and transformations, which is computationally infeasible due to the exponential number of possible operations.

Core Observation

Two strings can only be close if they have exactly the same set of unique characters, and the frequency counts of these characters can be rearranged to match each other. The allowed operations enable swapping characters and reassigning character identities but do not allow introducing or removing characters.

Path to Optimal

Preview

The key insight is to abstract away the actual characters and focus on two properties: the set of unique characters and the multiset of character frequencies. If the sets of characters differ, no sequence of operations can reconcile them…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Count the frequency of each character in both strings using hash maps (Counters). Compare the sets of keys (unique characters) for equality…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log n)

Counting frequencies with hash maps is O(n). Sorting the frequency lists dominates with O(k log k), where k is the number of unique characters, which is at most 26 for lowercase English letters, effectively O(1) in practice but O(n log n) in general.

Space

O(k)

Two hash maps store frequencies of up to k unique characters each, where k ≤ 26 for lowercase English letters, resulting in O(1) auxiliary space.

Solution

Python

1from collections import Counter
2
3class Solution:
4    def closeStrings(self, word1: str, word2: str) -> bool:
5        count1 = Counter(word1)
6        count2 = Counter(word2)
7
8        if set(count1.keys()) != set(count2.keys()):
9            return False
10
11        return sorted(count1.values()) == sorted(count2.values())

Step-by-Step Solution

1

Count Character Frequencies Using Hash Maps

5count1 = Counter(word1)
6count2 = Counter(word2)

Objective

To compute the frequency of each character in both input strings efficiently.

Key Insight

Using hash maps (Counters) to count character frequencies provides O(n) time complexity for frequency computation. This data structure captures both the unique characters present and their counts, which are essential for the subsequent comparison steps.

Interview Quick-Check

Core Logic

Counters provide a direct mapping from characters to their frequencies, enabling quick retrieval and comparison.

Complexity

Counting frequencies is O(n), where n is the length of the string, which is optimal.

2

Compare Unique Character Sets to Validate Transform Possibility

To verify that both strings contain exactly the same unique characters.

3

Compare Sorted Frequency Lists to Confirm Frequency Rearrangement

To determine if the frequency distributions of characters in both strings can be rearranged to match.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 8 Critical

if set(count1.keys()) != set(count2.keys()):

Check if the sets of unique characters in both strings are equal.

This condition ensures that both strings contain exactly the same characters, a necessary condition for the allowed transformations to be possible.

Line 11 Critical

return sorted(count1.values()) == sorted(count2.values())

Return true if sorted frequency lists match, false otherwise.

Comparing sorted frequency lists verifies that the frequency distributions can be rearranged to match, which is the final condition for the strings to be close under the allowed operations.

Line 9 Critical

return False

Return false immediately if unique character sets differ.

Early termination here prevents unnecessary computation when the strings cannot be close due to differing character sets.

Full line-by-line criticality + rationale for all 5 lines available on Pro.

Test Your Understanding

Why must the sets of unique characters in both strings be identical for them to be close?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Determine if Two Strings Are Close from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Determine if Two Strings Are Close drill

or drill a free problem

1	`from collections import Counter`
2
3	`class Solution:`
4	`def closeStrings(self, word1: str, word2: str) -> bool:`
5	`count1 = Counter(word1)`
6	`count2 = Counter(word2)`
7
8	`if set(count1.keys()) != set(count2.keys()):`
9	`return False`
10
11	`return sorted(count1.values()) == sorted(count2.values())`