Shamima Breaks Things
Algorithmic problems: Determine if two strings are close

Photo by Glenn Carstens-Peters on Unsplash

Algorithmic problems: Determine if two strings are close

Shamima Hossain's photo
Shamima Hossain
·

2 min read

Table of contents

Let's solve the second problem of December leetcoding https://leetcode.com/problems/determine-if-two-strings-are-close/ This is an Medium category problem which I struggled with a bit because of the question prompt as I couldn't figure out at first how to translate the two methods in code.

Problem breakdown

The problem tells us that we can make two seemingly different strings close by performing two 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

My approach

Turns out it was quite simple if we think about the bolded words. For the first operation, we need to make sure that the characters in both words are the same and for the second operation, the frequency of each of the characters is the same.

Data Structures used

I have used sets to compare the characters of the two words since sets don't allow duplicates and they take lesser time for searching. We also, take two hash_maps to store the character frequencies in each word and compare their counts.

Algorithms/ methods used

One additional check that I did at first is to see if the length of both words is equal if they are not then we have no reason to proceed further as it would never suffice the requirements. I iterate over both words and store their frequencies in two hash maps. Then we simply check if all the characters' frequencies are equal by sorting the frequency list and that the contents of the word sets are equal as well. We return True if it is the case and False otherwise.

def closeStrings(self, word1: str, word2: str) -> bool:
        if not len(word1) == len(word2):
            return False
        hash_map1 = {}
        for i, ch in enumerate(word1):
            if ch not in hash_map1:
                hash_map1[ch] = 1
            else:
                hash_map1[ch] += 1
        hash_map2 = {}
        for i, ch in enumerate(word2):
            if ch not in hash_map2:
                hash_map2[ch] = 1
            else:
                hash_map2[ch] += 1

        return sorted(hash_map1.values()) == sorted(hash_map2.values()) and hash_map1.keys() == hash_map2.keys()

Time and Space Complexity

The hash_maps take up extra space so O(n) space complexity

The sort costs O(nlogn) .

Although I must say, using python Counters can make the solution more elegant and shorter.

algorithmsPythonleetcodedata structures