LeetCode solution: Determine if Two Strings Are Close

Introduction

I was developing a solution for LeetCode today's challenge and decided to write this article to present a Python solution for the problem: 1657. Determine if Two Strings Are Close.

The 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.
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."

Check the link in the Introduction section if you want to see the complete problem statement with examples.

Note

Reading the problem statement might lead you to think that you need to implement the two operations to solve the challenge. However there are a few checks you can do instead of starting to implement and execute the operations described in the problem statement.

What to check to solve the problem

1. The first check is simple and easy: you need to make sure both strings word1 and word2 have the same length as neither operation would work correctly if they had different lengths.

2. The second check is: you need to check if the occurrences of each characters frequency are the same for both strings.
   For example, word1 = 'aabbcccc' and word2 = 'aabcbcaa' have the same number of occurrences in their character frequencies or, in other words, the same frequency of frequencies:
   

       # word1
       # chars frequency:
       {'c': 4, 'a': 2, 'b': 2}
       # frequency of frequencies:
       {2: 2, 4: 1}
   
       # word2
       # chars frequency:
       {'a': 4, 'b': 2, 'c': 2}
       # frequency of frequencies:
       {2: 2, 4: 1}
   

3. The third and last check is that all existing characters in one string must also exist in the other string.
   For example, word1 = 'aabbzzzz' and word2 = 'aabcbcaa' attend the second check related to the chars frequency. However the strings are not composed of the same characters ('z' doesn't exist in word2 just as 'c' doesn't exist in word1) and this is something that none of the operations described in the problem statement can solve.

My first solution

Following is the first solution I wrote to solve the problem:

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:        
        dict1 = dict()
        dict2 = dict()

        if len(word1) == len(word2):
            for char in word1:
                dict1[char] = dict1.get(char, 0) + 1
            for char in word2:
                dict2[char] = dict2.get(char, 0) + 1

            return sorted(dict1.values()) == sorted(dict2.values()) and set(dict1) == set(dict2)

        return False

Cleaning up and optimizing the solution

I did a few optimizations and also cleaned the code a little bit including the Counter module in my solution and tried to replace the sorted (which turns the complexity of the code into a nlog(n)) with some other way to improve the runtime complexity.
So I managed to optimize a little bit by rewriting it like this:

from collections import Counter

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:        
        dict1 = Counter(word1)
        dict2 = Counter(word2)

            return (
                len(word1) == len(word2) and 
                Counter(dict1.values()) == Counter(dict2.values()) and 
                set(dict1) == set(dict2)
            )

And if you want to go a little further and try to turn the solution into something even shorter, you can try this:

from collections import Counter

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:           
        return (
            len(word1) == len(word2) and
            Counter(Counter(word1).values()) == Counter(Counter(word2).values()) and
            set([*word1]) == set([*word2])
        )

Doing those changes improve the code runtime complexity which now is O(n).

Conclusion

To see more details about runtime and space complexity check out this same solution published on LeetCode The Hard Way.