Determine If Two Strings Are Close - Leetcode Solution

Problem:

Two strings are considered close if you can attain one from the other using the following operations:

• Operation 1: Swap any two existing characters.
• Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.

You are given two strings, word1 and word2. Return true if word1 and word2 are close, and false otherwise.

Solution:

To solve this problem, we need to check if the two strings have the same set of characters and the frequency of each character in both of them is same or not. We can perform two operations on the strings i.e. swap any two existing characters or transform every occurrence of one existing character into another existing character, and do the same with the other character.

Algorithm:

1. Check if the length of both strings is the same or not. If not, then they cannot be close. So, return False.

2. Count the frequency of each character in both strings. We can use a dictionary to store the frequency of each character.

3. Check if the set of characters in both strings are the same or not. If not, then they cannot be close. So, return False.

4. Calculate the frequency of each character in both strings. Iterate through both dictionaries and check if the frequency of each character is the same or not. If not, return False.

5. Return True if all steps are completed successfully.

Pseudo code:

def closeStrings(word1: str, word2: str) -> bool: if len(word1) != len(word2): return False freq_dict1 = {} freq_dict2 = {} for ch in word1: freq_dict1[ch] = freq_dict1.get(ch, 0) + 1 for ch in word2: freq_dict2[ch] = freq_dict2.get(ch, 0) + 1 if set(word1) != set(word2): return False freq_list1 = sorted(list(freq_dict1.values())) freq_list2 = sorted(list(freq_dict2.values())) if freq_list1 != freq_list2: return False return True

Time Complexity: O(N log N) where N is the length of string 1 or string 2. We are iterating over each character of both strings and sorting the frequency lists of both strings.

Space Complexity: O(N) where N is the length of string 1 or string 2. We are using two dictionaries to store the frequency of each character in strings.

1