Minimum Number of Steps to Make Two Strings Anagram

medium hash map string counting

Problem

Given two strings s and t of the same length, return the minimum number of characters in t you must replace so that t becomes an anagram of s.

Inputs = "leetcode", t = "practice"

Output5

Replace 5 characters in t (p, r, a, i, c) with letters from s.

def min_steps(s, t):
    cnt = [0] * 26
    for c in s: cnt[ord(c) - 97] += 1
    for c in t: cnt[ord(c) - 97] -= 1
    return sum(v for v in cnt if v > 0)

function minSteps(s, t) {
  const cnt = new Array(26).fill(0);
  for (const c of s) cnt[c.charCodeAt(0) - 97]++;
  for (const c of t) cnt[c.charCodeAt(0) - 97]--;
  let ans = 0;
  for (const v of cnt) if (v > 0) ans += v;
  return ans;
}

class Solution {
    public int minSteps(String s, String t) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        for (char c : t.toCharArray()) cnt[c - 'a']--;
        int ans = 0;
        for (int v : cnt) if (v > 0) ans += v;
        return ans;
    }
}

int minSteps(string s, string t) {
    int cnt[26] = {0};
    for (char c : s) cnt[c - 'a']++;
    for (char c : t) cnt[c - 'a']--;
    int ans = 0;
    for (int v : cnt) if (v > 0) ans += v;
    return ans;
}

Explanation

To turn t into an anagram of s, we only care about how many of each letter each string has, not the order. So the whole problem becomes a letter-counting exercise.

We keep one array cnt of 26 slots, one per letter. We add for every letter in s and subtract for every letter in t. After both passes, a slot that is positive means s has that many extra copies of that letter that t is missing.

Each missing letter in t can be fixed with exactly one replacement (swap one of t's surplus letters into the needed one). So the answer is simply the sum of the positive values.

Example: s = "leetcode", t = "practice". Counting up for s and down for t leaves positive entries that add up to 5, so 5 replacements are needed.

Because we never need the negatives (they are just t's surplus letters that will be overwritten), summing the positives alone gives the minimum number of steps.

Time: O(n) Space: O(1)