The Problem

This problem is described:

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.

Key Insights

This problem does not seem that approachable until coming to the following two key insights:

You can freely reorder the existing letters in a string by swapping any two existing letters. This is done through operation 1 in the problem description. For example, abcde -> aecdb .
You can also freely reassign the frequencies that any letter occurs. This is done by transforming every occurrence of one existing character into another existing character, and doing the same with the other character. This is done with operation 2 in the problem description. For example, aacabb -> bbcbaa , (all a's turn into b's, and all b's turn into a's).

These insights are not easy to come by at first glance. A good way to approach something like this is to play around with the two operations with a few example strings. While doing this, think about questions like:

What is the operation really doing?
Is there a more basic, more abstract way to describe what the operation is doing?

If that doesn't work, luckily for this problem, the two insights are listed in the hints for the problem.

Solution

Since you can freely reorder the strings, and freely reassign the frequencies of the letters to other letters, this means that you just need to find a way to test whether the strings consist of the same letters, and whether the letter frequencies (separate from any particular letters) are the same for both strings.

Here is one way to solve the problem, annotated with explanations along the way:

var closeStrings = function(word1, word2) {
    // If the strings are not the same length, return 
    // false as there is no way they'll be considered 
    // "close" per the problem description
    if (word1.length !== word2.length) 
        return false;

    /* Process each string with the helper function 
    getData (see below). The data1 & data2 variables get 
    assigned to an object returned by the function. That 
    object has an array of letters from the string and an 
    array of their frequencies, both sorted. The frequencies 
    are just an array of numbers, no longer associated with 
    any particular letter. */
    const data1 = getData(word1);
    const data2 = getData(word2);

    // Loop through the array of letters from data1, which 
    // came from processing the first string. 
    for (let i = 0; i < data1.ltrs.length; i++) {
        /* if the sorted arrays of letters from both strings 
        do not match, return false, or if the sorted arrays of 
        frequencies do not match, return false */
        if(data1.ltrs[i] !== data2.ltrs[i] 
           || data1.times[i] !== data2.times[i]) 
            return false;
    }
    // Otherwise, return true, since the two strings 
    // are considered "close"
    return true;
};

/* A helper function that is used above to process the 
strings and return an object {ltrs: [array of letters], 
times: [array of numbers representing frequencies that 
letters occurred in the string]} */
function getData(word) {
    /* Create an empty object. It will store letters from 
    a string as keys and the number of times they appear 
    in the string as values */
    const map = {};

    // Loop through the string
    for (const char of word) {
        // If the letter does not exist as a key in the 
        // map object, add it with a value of zero
        if(!map[char]) map[char] = 0;
        // Increase the value of the letter/key in the map 
        // object by 1. This is recording the number of times 
        // the letter occurs in the string
        map[char]++;
    }

    /* Return an object with the key ltrs containing an 
    array of the string's letters. The key times contains 
    an array of the number of times the letters occurred. 
    Times is just an array of numbers (the frequencies). 
    The point here is that we ultimately want to test if 
    the letters from both strings are the same. We will 
    also test if the frequencies - separate from and not 
    associated with any letters because they can be freely 
    reassigned - are also the same. */
    return {
        // ltrs gets assigned the keys of the map object 
        // (which are letters), sorted
        ltrs: Object.keys(map).sort(),
        /* times gets the values of the map object 
        (frequencies), sorted. The callback is passed to 
        the sort function to sort numbers properly, because 
        sort tries to sort values after converting to 
        strings, which can cause errors when sorting numbers. */
        times: Object.values(map).sort((a, b) => a - b)
    }
}
/* Note - the letters and frequencies are both sorted so 
that we can use a loop to compare whether they are the 
same as letters and frequencies in the other string above. 
Sorting makes it easy to loop through and check if the 
values of arrays for both strings are the same at the 
same index. */

Here is the solution without the comments:

var closeStrings = function(word1, word2) {
    if (word1.length !== word2.length) 
        return false;

    const data1 = getData(word1);
    const data2 = getData(word2);

    for (let i = 0; i < data1.ltrs.length; i++) {
        if(data1.ltrs[i] !== data2.ltrs[i] 
           || data1.times[i] !== data2.times[i]) 
            return false;
    }
    return true;
};

function getData(word) {
    const map = {};

    for (const char of word) {
        if(!map[char]) map[char] = 0;
        map[char]++;
    }

    return {
        ltrs: Object.keys(map).sort(),
        times: Object.values(map).sort((a, b) => a - b)
    }
}

How to solve the Leetcode 1657. Determine if Two Strings Are Close problem in JavaScript

Comments

More from this blog

The "best" git log command

How to add Google maps and markers to a React site

How to deploy a Ruby Sinatra Active Record app on Heroku

How to make a star rating display in React that's better than the one on yelp.com

The Problem

Key Insights

Solution

Command Palette

Comments

More from this blog

The Problem

Key Insights

Solution