1657. Determine if Two Strings Are Close

Determine if Two Strings Are Close 

Problem Description

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) Hashmap

/**
 * @param {string} word1
 * @param {string} word2
 * @return {boolean}
 */
var closeStrings = function(word1, word2) {
    if (word1.length !== word2.length)  return false;
    
    const chars = new Array(26).fill(0),
          used = new Array(26).fill(false),
          a = 'a'.charCodeAt(0);
    
    for (let i = 0; i < word1.length; i++) {
        chars[word1.charCodeAt(i)-a]++;
        used[word1.charCodeAt(i)-a] = true;
    }
    
    let countMap = {};
    
    for (let n of chars) {
        if (countMap[n] === undefined)
            countMap[n] = 0;
        countMap[n]++;
    }
    
    chars.fill(0);
    for (let i = 0; i < word2.length; i++) {
        if (!used[word2.charCodeAt(i)-a])  // if there is new char not used in word1, return false
            return false;
        chars[word2.charCodeAt(i)-a]++;
    }
    
    for (let n of chars) {
        if (countMap[n] === undefined)   // if one char has the frequency unused in word1, return false
            return false;
        countMap[n]--;
        if (countMap[n] < 0)
            return false;
    }
    
    return true;
};

Approach) XOR

• Create two arrays, count1 and count2, to count the occurrence of each character in word1 and word2.
• Check to make sure that word1 and word2 have the same set of unique characters, i.e. a character present in word1 must also be present in word2 and vice versa, if they don't then there is no way to transform word1 to word2.
  • We can do this by checking (count1[i] && !count2[i]) || (!count1[i] && count2[i]), which is essentially a XOR operation, so I'm gonna use Boolean(count1[i]) ^ Boolean(count2[i]) instead.
• Return true if count1 and count2 have the same frequency of characters since we are allowed to swap the occurrences with Operation 2.

/**
 * @param {string} word1
 * @param {string} word2
 * @return {boolean}
 */
var closeStrings = function(word1, word2) {
    if(word1.length !== word2.length) return false
    const count1 = new Array(26).fill(0)
    const count2 = new Array(26).fill(0)
    const a = 'a'.charCodeAt(0)
    for(let i=0; i<word1.length; i++){
        ++count1[word1.charCodeAt(i) - a]
        ++count2[word2.charCodeAt(i) - a]
    }
    for(let i=0; i<26; i++){
        if(Boolean(count1[i]) ^ Boolean(count2[i])) return false
    }
    return count1.sort().join('') === count2.sort().join('')
};

Approach) Greedy (Frequency Check)

This is actually a fairly simple problem. What we have to understand is that the first operation will allow us to rearrange the existing letters in any way whatsoever, so character positions don't matter at all. The second operation will allow you to change around the frequency assignment of any character whatsoever, so as long as the list of frequencies contains the same amounts, which character is assigned to which frequency doesn't matter.

The first easy check is whether or not the two words have the same length; if not, the evaluations returns false.

Next, we can pass the characters of both words into two separate frequency maps. Since there are only 26 allowable characters here and we can redesignate them as numbers, we can use an Array to be more efficient. We can also use bitmasking to more efficiently keep track of which characters have been seen for each word.

If the list of characters used on either side differs, then we can return false.

The easiest way to compare the list of frequencies is to sort both, convert to a string, and directly check their equivalency; if they differ, then return false.

Otherwise, the two words are a close match, so return true.

The best result for the code below is 76ms / 46.0MB.

Implementation:

The frequency maps will only need to contain non-negative integers, so we can use a more efficient Uint32Array.

Since there are only 26 characters for which we need to keep track of visited status, we can use a bitwise OR ( | ) operator and bitmasking (1 << n) to store that information in a single integer for each word.

That means we can iterate through the words together, convert the characters to 0-indexed numbers by using .charCodeAt(i) - 97, then update the frequency maps (fm1, fm2) and the visited information (vis1, vis2) for each word.

Then we can just perform our necessary comparisons and return the appropriate boolean value.

Code:

var closeStrings = function(A, B) {
    if (A.length !== B.length) return false
    let fm1 = new Uint32Array(26), vis1 = 0,
        fm2 = new Uint32Array(26), vis2 = 0
    for (let i = 0; i < A.length; i++) {
        let char1 = A.charCodeAt(i) - 97,
            char2 = B.charCodeAt(i) - 97
        fm1[char1]++, vis1 |= 1 << char1
        fm2[char2]++, vis2 |= 1 << char2
    }
    if (vis1 !== vis2) return false
    let sorted1 = fm1.sort((x,y) => x - y).join(''),
        sorted2 = fm2.sort((x,y) => x - y).join('')
    if (sorted1 !== sorted2) return false
    return true    
};

Bonus:

If you want even shorter code, you can push the duplicated code into a helper function.

var closeStrings = function(A, B) {
    const eval = word => {
        let len = word.length, fm = new Uint32Array(26), vis = 0
        for (let i = 0; i < len; i++) {
            let char = word.charCodeAt(i) - 97
            fm[char]++, vis |= 1 << char
        }
        return [len, vis, ...fm.sort((x,y) => x - y)].join(',')
    }
    return eval(A) === eval(B)
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 1657. Determine if Two Strings Are Close

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!