# blog.petefowler.dev # 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)
}
}
``````