Problem 1347

Question statement:

You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character. Return the minimum number of steps to make t an anagram of s.

Solution

Main idea:

Since the objective is to make t an anagram of s, all we need to focus on are the distinct letters in s, and their relative frequency. So we can build a dictionary that catures this information. Now, scanning through t, at letter t[i] we have one of two possibilities

• t[i] does not appear in s, so we need to replace this letter
• t[i] appears in s, but with multiplicity. We don’t replace this letter, but instead reduce the frequency (from our dictionary) by 1.
  • If at any point the frequency is 0, then we need to remove this letter from t.

Code:

def minSteps(self, s: str, t: str) -> int:
    dic = defaultdict(int)
    count = 0
    for i in s:
        dic[i] +=1

    for i in t:
        if(i not in dic):
            count+=1
        else: 
            if(dic[i]==0):
                count+=1
                continue
            dic[i]-=1
    return count

Comments:

Time complexity: O(max(len(s), len(t)))

At the time of submission, the above solution passes leetcode submission cases in 172ms, beating 54.53% of users. It uses 17.83MB of memory, beating 21.41% of users.