Watch 10 video solutions for Determine if Two Strings Are Close, a medium level problem involving Hash Table, String, Sorting. This walkthrough by codestorywithMIK has 19,272 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Two strings are considered close if you can attain one from the other using the following operations:
abcde -> aecdbaacabb -> 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 <= 105word1 and word2 contain only lowercase English letters.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 | Time | Space | When to Use |
|---|---|---|---|
| Compare Character Sets and Sorted Frequencies | O(n + k log k) | O(k) | Simple and clear implementation when sorting frequency lists is acceptable |
| Character Frequency Hashing | O(n + k) | O(k) | Optimal approach when avoiding sorting and maintaining strict linear complexity |