#1657

Medium

LeetCode Problem Workspace

Determine if Two Strings Are Close

Check if two strings can transform into each other using letter swaps and frequency reorganizations, leveraging hash tables.

hash table string sorting counting

Problem Statement

You are given two strings, word1 and word2. Two strings are considered close if you can transform one into the other by repeatedly applying the following operations: swap any two existing characters or transform all occurrences of one character into another existing character. You may apply these operations any number of times on either string.

Return true if word1 and word2 are close, otherwise return false. Each string consists only of lowercase English letters, and you must determine closeness based on character composition and frequency, not just sequence order.

Examples

Example 1

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

Output: true

You can attain word2 from word1 in 2 operations. Apply Operation 1: "abc" -> "acb" Apply Operation 1: "acb" -> "bca"

Example 2

Input: word1 = "a", word2 = "aa"

Output: false

It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3

Input: word1 = "cabbba", word2 = "abbccc"

Output: true

You can attain word2 from word1 in 3 operations. Apply Operation 1: "cabbba" -> "caabbb" Apply Operation 2: "caabbb" -> "baaccc" Apply Operation 2: "baaccc" -> "abbccc"

Constraints

1 <= word1.length, word2.length <= 105
word1 and word2 contain only lowercase English letters.

Solution Approach

Count Character Frequencies

Use a hash table to store the frequency of each character in both strings. This helps identify whether the same set of letters exists and prepares for frequency comparison. Missing or extra letters immediately indicate the strings are not close.

Compare Character Sets

Extract the unique characters from both strings and compare them. If the sets differ, transformation is impossible, so return false. This step catches mismatches early, avoiding unnecessary operations.

Compare Frequency Multisets

Sort the frequency values from both hash tables and compare. If the sorted lists match, the strings are close since Operation 1 allows any ordering and Operation 2 permits frequency swapping. Otherwise, return false.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n + m + k log k), where n and m are the lengths of word1 and word2, and k is the number of unique characters; sorting frequencies dominates. Space complexity is O(k) for hash tables storing character counts.

What Interviewers Usually Probe

Check if both strings contain exactly the same set of letters.
Consider if the character frequency distributions are compatible.
Watch out for edge cases with repeated single letters or mismatched lengths.

Common Pitfalls or Variants

Common pitfalls

Assuming order of letters matters; Operation 1 allows free reordering.
Ignoring letters that exist in one string but not the other.
Comparing raw frequency dictionaries without sorting the values.

Follow-up variants

Determine closeness when strings include uppercase letters or digits.
Compute minimal number of operations needed to make strings close.
Check closeness under limited number of allowed swaps or transformations.

FAQ

What does 'Determine if Two Strings Are Close' mean in algorithm terms?

It means checking if you can transform one string into the other using unlimited swaps and character frequency substitutions, focusing on hash table frequency patterns.

Why compare sorted frequency values instead of raw counts?

Sorting allows you to match frequency distributions without caring about which specific letters hold each count, aligning with allowed transformations.

Does the order of letters in the strings matter?

No, Operation 1 permits free reordering, so only character presence and counts influence closeness.

Can strings with different lengths ever be close?

No, strings must be of equal length to allow transformations; differing lengths immediately return false.

Is a hash table always required for this problem?

While not strictly required, hash tables make counting and comparing character frequencies efficient and clear, matching the Hash Table plus String pattern.

terminal

Solution

Solution 1: Counting + Sorting

According to the problem description, two strings are close if they meet the following two conditions simultaneously:

1

2

3

4

5

6

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

Continue Practicing

#1366 rank teams by votes #767 reorganize string #692 top k frequent words