LeetCode Challenge #1657. Determine if Two Strings Are Close

Question 22 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #1657. Determine if Two Strings Are Close

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 <= 10⁵
word1 and word2 contain only lowercase English letters.

Video Solution

C++ Solution

				
					class Solution {
public:
    bool closeStrings(string word1, string word2) {

        unordered_map<int,int> map1,map2;

        if(word1.length()!=word2.length()) return false;

        for(int i=0; i<word1.size(); i++) map1[word1[i]]++;
        for(int i=0; i<word2.size(); i++) map2[word2[i]]++;

        for(int i=0; i<word1.size(); i++)
        {
            if(map2.find(word1[i])==map2.end()) return false;
        }
        for(int i=0; i<word2.size(); i++)
        {
            if(map1.find(word2[i])==map1.end()) return false;
        }

        vector<int> vect1,vect2;

        for(auto i:map1) vect1.push_back(i.second);
        for(auto i:map2) vect2.push_back(i.second);

        sort(vect1.begin(),vect1.end());
        sort(vect2.begin(),vect2.end());

        return vect1==vect2;
    }
};

Code Explanation

The purpose of this function is to determine whether two strings, ‘word1’ and ‘word2’, are close under certain conditions. Two words are considered close if they have the same set of characters and the frequencies of these characters are also the same.

We will initialise two unordered maps, ‘map1’ and ‘map2 ‘, to store the frequency of each character in the two words, ‘word1’ and ‘word2’.

Now, if the lengths of the two words are not equal, the function immediately returns ‘false’.

Now, we will use a for loop that iterates through each character of ‘word1’ and ‘word2’, populating the frequency maps, ‘map1’ and ‘map2’.
Now, we have to check that both words have the same set of characters by iterating through each character in one word and checking if it exists in the other. If any character is found in one word but not in the other, the function returns ‘false’.

The same process will be repeated for ‘word2’ also.

Next, we will check for the common characters. This can be done in the way that both words have the same set of characters, by iterating through each character and checking if it exists in the other. If it does, that means if any character is found in one word but not in the other, the function returns ‘false’.

After ensuring that our first condition is fulfilled and that existence will be there or not, we will check for the second condition.

Now, we have to check the occurrence of the characters. We will make two vectors namely ‘vect1’ and ‘vect2’. And iterate them by occurrences; the same process will be repeated for word 2.
Now, we have to sort both of the arrays, and if ‘vect1’ is equal to ‘vect2’ that means the string can be swapped, and if not, then the string cannot be swapped. So, return ‘vect1 ==vect2’

Question 22 of 75 - LeetCode Weekly Challenge