[Problem] Determine if Two Strings Are Close

leetcode.com/problems/determine-if-two-strings-are-close/

Problem Statement

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.

Example

Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations.
Apply Operation 1: "abc" -> "acb"
Apply Operation 1: "acb" -> "bca"

Approach

While the problem seems complicated from the variety of operations, the problem becomes simple if we focus on the idea that both operations are 'unlimited' and can be used on either target string.

Hence, we only need to check if the strings satisfy the following conditions:

1. Every character in word1 must be present in word2.
2. The frequency of all the characters is always the same.

Since Python does not have an in-built multiset, we will be using dictionaries to keep track of the frequencies of all characters in each word, and then compare the resultant dictionaries.

Also, at the top of code, we will go through a process where we check the characters in word1 is present in word2.

Solution

class Solution(object):
    def closeStrings(self, word1, word2):
        count1 = defaultdict(int)
        count2 = defaultdict(int)
        freq_col1 = defaultdict(int)
        freq_col2 = defaultdict(int)
        
        for i in word1:
            if i not in word2: return False

        for c in word1:
            count1[c] += 1
        
        for c in word2:
            count2[c] += 1
        
        for key in count1:
            freq_col1[count1[key]] += 1

        for key in count2:
            freq_col2[count2[key]] += 1

        return freq_col1 == freq_col2