LeetCode solution: Determine if Two Strings Are Close
Tags: leetcode, algorithms, programming, python
Published: 2022-12-02 17:45:58

## 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](https://leetcode.com/problems/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:

    ```Python
        # 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:

```Python
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:

```Python
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:

```Python
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](https://wingkwong.github.io/leetcode-the-hard-way/solutions/1600-1699/define-if-two-strings-are-close-medium).