Problem 1657

Question statement:

Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise. 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.

Solution

Main idea:

Since we are allowed to do the operations as many times as we like, the first operation can be interpreted as a saying that we can rearrange the characters as we please, and the second operation allows us to freely reassign the frequency of a character (to some other number that appears in the list of initial frequencies). Thus to see if the two words are anagrams of each other, we want:

• All the distinct letters in both words to be the same
• The initial frequency lists of distinct characters for both words should be equal (as multisets).

This can be programattically achieved by creating a dictionary, or as I have recently learned, by using a built in function Counter() that automatically creates a frequency dictionary via a single function call.

After creating a frequency dictionary, we verify the first item by checking if the keys of both dictionaries are equal (as sets). Then, for the second item, we have a pretty slick approach: Take the values of both dictionaries as a list, and then create a frequency dictionary of these two lists. If these dictionaries agree, then we know that the frequency lists are equal (as multisets), so we return True. Otherwise we return False.

Note: The slick approach works because: If the keys of the second counter disagree, then as sets the will frequencies disagree. If the keys agree, but the corresponding frequencies disagree, then the multiplicities of a particular frequency disagree, which in turn tells us that the frequencies disagree as multisets.

Code:

def closeStrings(self, word1: str, word2: str) -> bool:
    c1 = Counter(word1)
    c2 = Counter(word2)
    if c1.keys() == c2.keys():
        return Counter(list(c1.values())) == Counter(list(c2.values()))
    return False

Comments:

Time complexity: O(max(len(word1), len(word2))) (creation of Counter is linear time)

At the time of submission, the above solution passes leetcode submission cases in 111ms, beating 96.33% of users. It uses 18.38MB of memory, beating 28.83% of users.