Leetcode 1657. Determine if Two Strings Are Close

Problem Explanation

The problem is asking us to determine if we can transform one string into another using some specific operations. These operations are:

Operation 1: Swapping any two existing characters in the string. For example, 'abcd' can become 'acbd' by swapping 'b' and 'c'.

Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character. For example, 'aabbaa' can become 'bbaabb' by transforming all 'a's to 'b's and all 'b's to 'a's.

The transformed string does not need to be a valid word, and any number of operations can be used (including none). If it is possible to transform the first string into the second using these operations, we should return true; otherwise, we should return false.

Solution Approach

The approach for this problem involves comparing character counts and character frequencies in the two strings.

First, if the lengths of the two strings are not the same, we return false directly, because it's impossible to attain one string from another with unequal lengths by applying the操作中.

Then we count the frequency of each character in both strings, and collect all unique characters and their respective frequencies.

Next, we sort these two lists of unique characters, and compare them. If they are not identical, we return false. This is because we can't swap or transform characters that don't exist in the other string.

Finally, we sort the two frequency lists and compare them. If they are identical, we return true; otherwise, we return false. The reason is that, with Operations 1 and 2, we can always swap and transform characters within the same string to make their frequencies match those in the other string, given that the unique characters in both strings are the same.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  bool closeStrings(string word1, string word2) {
6    if (word1.length() != word2.length())
7      return false;
8
9    unordered_map<char, int> count1;
10    unordered_map<char, int> count2;
11    vector<int> freqs1;  // Freqs of unique chars in word1
12    vector<int> freqs2;  // Freqs of unique chars in word2
13
14    for (char c : word1)
15      count1[c]++;
16
17    for (char c : word2)
18      count2[c]++;
19
20    for (auto& [c, freq] : count1)
21      freqs1.push_back(freq);
22
23    for (auto& [c, freq] : count2)
24      freqs2.push_back(freq);
25
26    sort(freqs1.begin(), freqs1.end());
27    sort(freqs2.begin(), freqs2.end());
28
29    return freqs1 == freqs2 && unordered_set<char>(word1.begin(), word1.end()) == unordered_set<char>(word2.begin(), word2.end());
30  }
31};

Java Solution

1
2java
3public class Solution {
4    public boolean closeStrings(String word1, String word2) {
5        if (word1.length() != word2.length())
6            return false;
7
8        int[] freq1 = new int[26];
9        int[] freq2 = new int[26];
10        for (char c : word1.toCharArray())
11            freq1[c - 'a']++;
12
13        for (char c : word2.toCharArray())
14            freq2[c - 'a']++;
15
16        Arrays.sort(freq1);
17        Arrays.sort(freq2);
18
19        return Arrays.equals(freq1, freq2) && word1.chars().distinct().sorted().equals(word2.chars().distinct().sorted());
20    }
21}

Python Solution

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

JavaScript Solution

1
2javascript
3var closeStrings = function(word1, word2) {
4    if (word1.length !== word2.length) return false;
5    
6    const count1 = new Array(26).fill(0);
7    const count2 = new Array(26).fill(0);
8
9    for (let i = 0; i < word1.length; i++) {
10        count1[word1.charCodeAt(i) - 97]++;
11        count2[word2.charCodeAt(i) - 97]++;
12    }
13
14    count1.sort((a, b) => a - b);
15    count2.sort((a, b) => a - b);
16
17    return count1.every((val, i) => val === count2[i]) && 
18    count1.some((val, i) => val !== 0 || count2[i] !== 0);
19};

Explanation

This solution follows the same approach to solve the problem but in JavaScript. We initialize two new arrays count1 and count2 of size 26 (as there are 26 alphabets) with zero.

Using the ASCII value of the character (subtracted by 97 to start indexing from 0 for 'a') as the index of the arrays, we increment the values for each character's frequency in the respective words.

After sorting both the count arrays, we check if every corresponding value in the arrays is the same, and if there is at least one non-zero value present (which ensures there are some alphabets in the input string). If both conditions are true, we can transform one string to another, hence returning true, otherwise false.

The time complexity of this solution is O(n log n) due to sorting, where n is the length of the string. The space complexity is O(1) as the size of the arrays is constant.

In all four discussed solutions (C++, Python, Java, and JavaScript), we essentially check the frequency counts and distinct characters' set in both input strings to decide whether we can transform one string to another. The implementation differs due to the language-specific features and built-in methods.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫