10.16 Minimum Number of Steps to Make Two Strings Anagram

10.16.1 Problem Metadata

10.16.2 Description

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) permutation.

10.16.3 Examples

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.

10.16.4 Constraints

  • 1 <= s.length <= 5 * 10^4
  • s.length == t.length
  • s and t consist of lowercase Englc-lish letters only

10.16.5 Solution

10.16.5.1 Walkthrough

To make t an anagram of s, both strings must have identical character frequencies. The solution uses a frequency counting approach:

  1. Count the frequency of each character in both strings using arrays of size 26 (for lowercase Englc-lish letters)
  2. Compare frequencies: for each character, if s has more occurrences than t, those represent characters that t is missing
  3. Sum the differences where s_freq[i] > t_freq[i] - this gives the minimum number of replacements needed

Key Insight: We only count characters that s has but t lacks (or has fewer of). Characters that t has in excess will automatically be replaced by the missing characters, so we don’t need to count them separately.

Example: For s = "bab" and t = "aba": - s_freq: a=1, b=2 - t_freq: a=2, b=1 - Difference: b appears 1 more time in s → need 1 replacement - Result: 1

10.16.5.2 Analysis

  • Time Complexity: O(n) where n is the length of the strings
    • Two passes to count frequencies: O(n) each
    • One pass through the 26-element frequency array: O(26) = O(1)
    • Total: O(2n + 26) = O(n)
  • Space Complexity: O(1)
    • Two fixed-size arrays of 26 integers each
    • Space does not scale with input size
    • Total: O(52) = O(1)

10.16.5.3 Implementation Steps

  1. Create a helper method countLetterFrequency(String) that returns a frequency array for a given string
  2. Count character frequencies for both s and t using the helper method
  3. Initialize a result counter to 0
  4. Iterate through the 26 possible characters (a-z)
  5. For each character, if s_freq[i] > t_freq[i], add the difference to result
  6. Return result as the minimum number of steps

10.16.5.4 Code - Java

class Solution {
    public int minSteps(String s, String t) {
        int[] s_freq = countLetterFrequency(s);
        int[] t_freq = countLetterFrequency(t);
        int result = 0;

        for(int i = 0; i < 26; i++) {
            if(s_freq[i] > t_freq[i]) {
                result += s_freq[i] - t_freq[i];
            }
        }

        return result;
    }

    private int[] countLetterFrequency(String str) {
        int[] freq = new int[26];

        for(char c : str.toCharArray()) {
            freq[c - 'a']++;
        }

        return freq;
    }
}