1347. Minimum Number of Steps to Make Two Strings Anagram - Detailed Explanation

Problem Statement

Given two strings s and t of equal length consisting of lowercase English letters, the goal is to make t an anagram of s by replacing characters in t. In one step, you can choose any character from t and change it to any other lowercase letter. You need to return the minimum number of such steps required so that t becomes an anagram of s.

Examples

Example 1

• Input: s = "bab", t = "aba"
• Output: 1
• Explanation:
  • Frequency in s: {'b': 2, 'a': 1}
  • Frequency in t: {'a': 2, 'b': 1}
  • In t, there is one extra 'a' compared to s. Changing that extra 'a' to 'b' makes t an anagram of s.

Example 2

• Input: s = "leetcode", t = "practice"
• Output: 4
• Explanation:
  • Frequency in s: {'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1}
  • Frequency in t: {'p': 1, 'r': 1, 'a': 1, 'c': 2, 't': 1, 'i': 1, 'e': 1}
  • In t, there is an extra 'c' (one extra occurrence) and extra occurrences of letters that do not appear in s (like 'p', 'r', 'a', and 'i').
  • Replacing these extra characters (a total of 4 changes) will make t an anagram of s.

Example 3

• Input: s = "anagram", t = "mangaar"
• Output: 0
• Explanation:
  • Both strings have the same frequency of each character, meaning t is already an anagram of s. No changes are needed.

Constraints

• The lengths of s and t are equal.
• Both s and t consist of lowercase English letters.

Hints

1. Frequency Counting: An anagram requires that both strings have identical character frequencies. Consider counting how many times each character appears in both strings.

2. Focus on Surplus: Since you are only allowed to change characters in t, identify which characters in t occur more times than in s. The sum of these excess counts will be the minimum number of steps needed.

Approach 1: Counting Frequencies (Optimal Solution)

Explanation

1. Count Frequencies:

   • Use an array (or hash map) of size 26 (one for each lowercase letter) to count the occurrences in s and t.

2. Determine Excess Characters:

   • For every character, if t contains more instances than s, the extra characters need to be replaced.
   • Calculate the difference:
     • For character ch, if count_t[ch] > count_s[ch], then count_t[ch] - count_s[ch] is the number of steps required for that character.

3. Sum the Differences:

   • The total minimum number of steps is the sum of these differences over all characters.

Visual Example (Example 1: s = "bab", t = "aba")

• Step 1: Count frequencies
  • s: {'b': 2, 'a': 1}
  • t: {'a': 2, 'b': 1}
• Step 2: Compare counts for each letter
  • For 'a': t has 2 and s has 1 → excess = 1
  • For 'b': t has 1 and s has 2 → no excess (ignore negative differences)
• Step 3: Total steps = 1

Code in Python

Below is the Python implementation of the optimal solution using frequency counting.