## DEV Community 👩‍💻👨‍💻

Jessica Alves

Posted on • Updated on

# 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.