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.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:
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.
JavaScript
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.
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.
C#
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.
| Approach | Complexity |
|---|---|
| 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. |
Leetcode 1657. Determine if Two Strings Are Close • Fraz • 14,621 views views
Watch 9 more video solutions →Practice Determine if Two Strings Are Close with our built-in code editor and test cases.
Practice on FleetCode