1347. Minimum Number of Steps to Make Two Strings Anagram

[sophryu99]

Approach

https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/description/

Anagram: Words that can be rearranged to form each others

1. Store the frequency of the letters in both strings in a dictionary
2. From a dict that has more unique letters, subtract the frequencies
3. Sum of the remaining dictionary values will be the min number of steps to make two strings anagram

from collections import defaultdict
class Solution:
    def minSteps(self, s: str, t: str) -> int:
        s_dict = defaultdict(int)
        t_dict = defaultdict(int)

        for i in range(len(s)):
            s_dict[s[i]] += 1
            t_dict[t[i]] += 1

        s_count = len(set(s_dict))
        t_count = len(set(t_dict))
        res = 0
        if s_count > t_count:
            for item in s_dict:
                if item in t_dict:
                    s_dict[item] = max(0, s_dict[item] - t_dict[item]) 

            res = sum(s_dict.values())
        else:
            for item in t_dict:
                if item in s_dict:
                    t_dict[item] = max(0, t_dict[item] - s_dict[item]) 

            res = sum(t_dict.values())

        return res

N: length of the strings

• Time Complexity: O(n) linear scan through the strings
• Space Complexity: O(n) dictionaries