Skip to main content
Talentd

Determine if Two Strings Are Close - Solution & Explanation

MediumHash TableStringSortingCounting14 min readAsked at: Amazon, Microsoft, Apple +4
Practice this problem

Problem Statement

Two strings are considered close if you can attain one from the other using the following operations:

  • Operation 1: Swap any two existing characters.
    • For example, abcde -> aecdb
  • Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
    • For example, aacabb -> bbcbaa (all a's turn into b's, and all b's turn into a's)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

 

Example 1:

Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: 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
Explanation: 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
Explanation: 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.

Approach Overview

Problem Overview: You are given two strings word1 and word2. Two strings are considered close if you can transform one into the other using two operations: swap any two characters, or transform every occurrence of one character into another existing character and vice versa. The task is to determine if such transformations can make the strings identical.

Approach 1: Compare Character Sets and Frequency (O(n + k log k) time, O(k) space)

The key observation is that transformations allow characters to be rearranged freely and also allow swapping frequency distributions between characters. Because of this, two conditions must hold. First, both strings must contain the exact same set of characters. If a character exists in one string but not the other, no operation can introduce it. Second, the frequency distributions of characters must match when sorted. Build frequency maps using a hash table, compare the character sets, then sort the frequency lists and check equality. Sorting the counts ensures that frequency patterns match even if the characters themselves differ.

Approach 2: Character Frequency Hashing (O(n + k) time, O(k) space)

This approach avoids sorting and instead relies on counting frequencies efficiently. Use two arrays or hash maps to count occurrences of each character while iterating through the strings once. Verify the character presence condition first by checking that both strings share the same character set. Then compare the multiset of frequency counts by hashing the counts themselves (for example using another map of frequency-of-frequency). Because the alphabet size k is small (26 lowercase letters), this runs in linear time relative to the string length. This technique relies heavily on counting and efficient lookups with a hash table.

Recommended for interviews: Interviewers typically expect the frequency-count insight. Start by confirming both strings share the same unique characters, then compare their frequency distributions. The sorted-frequency method is easy to reason about and widely accepted. The hashing approach demonstrates stronger understanding of string processing and counting patterns while maintaining linear time complexity.

Approach 1: Compare Character Sets and Frequency

To check whether two strings are close, you must determine if they can be made identical using the allowed operations. These operations permit swapping characters or changing all instances of one character to another, as long as they are existing characters in the particular string. Therefore, for two strings to be close:

  • They must contain the exact same set of unique characters.
  • The frequency of characters, when sorted, should be identical; this indicates that you can transform one frequency distribution into the other via swaps.

Thus, comparing the character sets and their frequency distributions will be sufficient to determine if the strings are close.

This solution first checks if the strings have the same length, as differing lengths would make it impossible for them to be close. It then uses Python's Counter to count the occurrences of each character in both strings. The first condition checks if both strings have the same set of unique characters using the keys() method, which returns a set of unique characters. The second condition checks if the frequency distributions are identical by sorting and comparing the counted values.

Code

PythonJavaScript

Python

JavaScript

Complexity

The time complexity is O(n + m), where n and m are the lengths of the strings, due to counting characters and comparing sets. Sorting the frequencies has a time complexity of O(k log k), where k is the number of unique characters. The space complexity is O(1) since we only store counts for at most 26 characters.

Try this approach in the editor →

Approach 2: Character Frequency Hashing

Alternative to directly sorting the character frequencies to compare them, we can map frequencies to counts using an intermediate structure, effectively hashing the frequency occurrences. This approach ensures that both overall character sets and their frequency distributions align.

Here, we first count the characters like before and then extract the keys into sets and compare them for equality. We use a HashMap to count the frequency of frequencies themselves, comparing these two frequency maps. Equal keys signify a valid transformation is possible between the two frequency distributions.

Code

JavaC#

Java

C#

Complexity

The time complexity remains O(n + m) due to creating and comparing maps, with a space complexity of O(1) due to counting up to 26 character frequencies.

Try this approach in the editor →

Approach 3: Counting + Sorting

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

  1. The strings word1 and word2 must contain the same types of letters.
  2. The arrays obtained by sorting the counts of all characters in word1 and word2 must be the same.

Therefore, we can first use an array or hash table to count the occurrences of each letter in word1 and word2 respectively, and then compare whether they are the same. If they are not the same, return false early.

Otherwise, we sort the corresponding counts, and then compare whether the counts at the corresponding positions are the same. If they are not the same, return false.

At the end of the traversal, return true.

The time complexity is O(m + n + C times log C), and the space complexity is O(C). Here, m and n are the lengths of the strings word1 and word2 respectively, and C is the number of letter types. In this problem, C=26.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Compare Character Sets and Frequency

The time complexity is O(n + m), where n and m are the lengths of the strings, due to counting characters and comparing sets. Sorting the frequencies has a time complexity of O(k log k), where k is the number of unique characters. The space complexity is O(1) since we only store counts for at most 26 characters.

Character Frequency Hashing

The time complexity remains O(n + m) due to creating and comparing maps, with a space complexity of O(1) due to counting up to 26 character frequencies.

Counting + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Compare Character Sets and Sorted FrequenciesO(n + k log k)O(k)Simple and clear implementation when sorting frequency lists is acceptable
Character Frequency HashingO(n + k)O(k)Optimal approach when avoiding sorting and maintaining strict linear complexity

Video Solution

Determine if Two Strings Are Close | Intuition | Google | Leetcode 1657 • codestorywithMIK • 20,773 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Determine if Two Strings Are Close easy or hard?
Determine if Two Strings Are Close is classified as a Medium difficulty problem. The challenge lies in recognizing that the operations allow arbitrary swaps and frequency exchanges, which reduces the problem to comparing character sets and frequency distributions.
Determine if Two Strings Are Close Python/Java solution
In Python, developers typically use collections.Counter or arrays to count characters and compare sorted frequency values. In Java, HashMap or int[26] arrays are common for counting characters and verifying frequency distributions efficiently.
How to solve Determine if Two Strings Are Close in O(n)?
Count the frequency of each character in both strings using arrays or hash maps. Verify that both strings contain the same set of characters. Then compare their frequency distributions using a hash-based comparison instead of sorting. This keeps the algorithm O(n) with O(k) extra space.
What is the best approach for Determine if Two Strings Are Close?
The most common approach compares the set of characters and the distribution of their frequencies. First check that both strings contain the same unique characters. Then compare the sorted frequency counts. If both conditions match, the strings are close. This runs in O(n + k log k) time where k is the alphabet size.
Is Determine if Two Strings Are Close asked at Google/Amazon/Meta?
String frequency and transformation problems like this appear frequently in interviews at companies such as Amazon, Meta, and Google. They test understanding of hash maps, counting techniques, and reasoning about allowed operations on strings.
What data structure is used in Determine if Two Strings Are Close?
The solution primarily uses hash tables or fixed-size frequency arrays to count characters. Sorting may also be used to compare frequency distributions. These structures allow efficient counting and constant-time lookups.
What is the time complexity of Determine if Two Strings Are Close?
The optimal solution runs in O(n) time for counting characters plus a small overhead based on the alphabet size. Using sorted frequency comparison gives O(n + k log k) time. Since k is at most 26 for lowercase letters, both approaches are effectively linear.

Ready to solve this problem?

Practice Determine if Two Strings Are Close with our built-in code editor and test cases.

Practice on FleetCode
Previous

Buddy Strings

Next

Minimum Number of Steps to Make Two Strings Anagram