Leetcode problem 125 - Minimum Number of Steps to Make Two Strings Anagram

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.

An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.

Example 1:

Input: s = “bab”, t = “aba” Output: 1 Explanation: Replace the first ‘a’ in t with b, t = “bba” which is anagram of s. Example 2:

Input: s = “leetcode”, t = “practice” Output: 5 Explanation: Replace ‘p’, ‘r’, ‘a’, ‘i’ and ‘c’ from t with proper characters to make t anagram of s. Example 3:

Input: s = “anagram”, t = “mangaar” Output: 0 Explanation: “anagram” and “mangaar” are anagrams.

Constraints:

1 <= s.length <= 5 * 104 s.length == t.length s and t consist of lowercase English letters only.

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var minSteps = function (s, t) {
  let obj = {};

  for (let ch of s) {
    if (!obj[ch]) {
      obj[ch] = 0;
    }
    ++obj[ch];
  }

  for (let ch of t) {
    if (obj[ch]) {
      --obj[ch];
    }
  }

  let arr = Object.values(obj);
  let result = arr.reduce((acc, val) => acc + val, 0);

  return result;
};

The time complexity of this code is O(n), where n is the length of string s and m is the length of string t. This is because we iterate through both strings s and t once to populate the obj object, and then iterate through string t to decrement the counts in obj. The overall time complexity is dominated by the length of the longer string between s and t.

The space complexity of this code is O(n), where k is the number of unique characters in strings s and t. This is because we are using the obj object to store the counts of each character in string s, and the space required is proportional to the number of unique characters in both strings.