medium Minimum Number of Steps to Make Two Strings Anagram

Problem Statement

Given two strings, s and t, of the same length, return the minimum number of steps required to make t an anagram of s.

In each step, you can replace any character in t with another character.

An anagram of a string is a string that contains the same characters in any order.

Examples

Example 1:

• Input: s = "designgurus", t = "garumdespgn"
• Expected Output: 3
• Justification: We need to replace a, m, and p characters in the string t to match the frequency of characters in s.

Example 2:

• Input: s = "abc", t = "def"
• Expected Output: 3
• Justification: We need to replace all three characters in t to match those in s.

Example 3:

• Input: s = "listen", t = "silent"
• Expected Output: 0
• Justification: The string t is already an anagram of s.

Constraints:

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

Solution

To solve this problem, we use a HashMap to keep track of the frequency differences between the characters in two strings, s and t. The idea is to increment the frequency count for each character in t and decrement it for each character in s. This will give us a map with the net frequency difference for each character. By summing up the positive differences, we can determine the minimum number of steps required to make t an anagram of s.

This method ensures that we efficiently count and compare character frequencies, making the solution both time-efficient and easy to implement.

Step-by-step Algorithm

1. Initialize Frequency Difference Map:

   • Create a map to store the frequency difference of characters between the two strings. This map will help track how many characters need to be added or removed to make the strings anagrams of each other.

2. Count the Frequency Differences:

   • For each character in the strings s and t:
     • Increment the count for the character in t in the frequency difference map.
     • Decrement the count for the character in s in the frequency difference map.
     • This step helps identify the characters that are in excess or deficit in t compared to s.

3. Calculate the Number of Steps Needed:

   • Initialize a variable steps to 0. This will keep track of the number of characters that need to be replaced.
   • For each count in the frequency difference map:
     • If the count is positive, add it to steps. This represents the characters in t that are in excess and need to be replaced to match s. In this step, the excess characters of string s will be replaced by the excess characters of string t. So, we don't need to count them.

4. Return the Result:

   • Return the value of steps, which represents the minimum number of character replacements needed to make t an anagram of s.

Algorithm Walkthrough

Using the input:

• s = "designgurus"
• t = "garumdespgn"

1. Initialization:

   • frequencyDifference = {}

2. Traverse both strings and update frequency differences:

   • i = 0:
     • charT = 'g', charS = 'd'
     • Increment frequency of 'g': frequencyDifference.put('g', 1)
     • Decrement frequency of 'd': frequencyDifference.put('d', -1)
     • frequencyDifference = {'g': 1, 'd': -1}
   • i = 1:
     • charT = 'a', charS = 'e'
     • Increment frequency of 'a': frequencyDifference.put('a', 1)
     • Decrement frequency of 'e': frequencyDifference.put('e', -1)
     • frequencyDifference = {'g': 1, 'd': -1, 'a': 1, 'e': -1}
   • i = 2:
     • charT = 'r', charS = 's'
     • Increment frequency of 'r': frequencyDifference.put('r', 1)
     • Decrement frequency of 's': frequencyDifference.put('s', -1)
     • frequencyDifference = {'g': 1, 'd': -1, 'a': 1, 'e': -1, 'r': 1, 's': -1}
   • i = 3:
     • charT = 'u', charS = 'i'
     • Increment frequency of 'u': frequencyDifference.put('u', 1)
     • Decrement frequency of 'i': frequencyDifference.put('i', -1)
     • frequencyDifference = {'g': 1, 'd': -1, 'a': 1, 'e': -1, 'r': 1, 's': -1, 'u': 1, 'i': -1}
   • i = 4:
     • charT = 'm', charS = 'g'
     • Increment frequency of 'm': frequencyDifference.put('m', 1)
     • Decrement frequency of 'g': frequencyDifference.put('g', 0)
     • frequencyDifference = {'g': 0, 'd': -1, 'a': 1, 'e': -1, 'r': 1, 's': -1, 'u': 1, 'i': -1, 'm': 1}
   • i = 5:
     • charT = 'd', charS = 'n'
     • Increment frequency of 'd': frequencyDifference.put('d', 0)
     • Decrement frequency of 'n': frequencyDifference.put('n', -1)
     • frequencyDifference = {'g': 0, 'd': 0, 'a': 1, 'e': -1, 'r': 1, 's': -1, 'u': 1, 'i': -1, 'm': 1, 'n': -1}
   • i = 6:
     • charT = 'e', charS = 'g'
     • Increment frequency of 'e': frequencyDifference.put('e', 0)
     • Decrement frequency of 'g': frequencyDifference.put('g', -1)
     • frequencyDifference = {'g': -1, 'd': 0, 'a': 1, 'e': 0, 'r': 1, 's': -1, 'u': 1, 'i': -1, 'm': 1, 'n': -1}
   • i = 7:
     • charT = 's', charS = 'u'
     • Increment frequency of 's': frequencyDifference.put('s', 0)
     • Decrement frequency of 'u': frequencyDifference.put('u', 0)
     • frequencyDifference = {'g': -1, 'd': 0, 'a': 1, 'e': 0, 'r': 1, 's': 0, 'u': 0, 'i': -1, 'm': 1, 'n': -1}
   • i = 8:
     • charT = 'p', charS = 'r'
     • Increment frequency of 'p': frequencyDifference.put('p', 1)
     • Decrement frequency of 'r': frequencyDifference.put('r', 0)
     • frequencyDifference = {'g': -1, 'd': 0, 'a': 1, 'e': 0, 'r': 0, 's': 0, 'u': 0, 'i': -1, 'm': 1, 'n': -1, 'p': 1}
   • i = 9:
     • charT = 'g', charS = 'u'
     • Increment frequency of 'g': frequencyDifference.put('g', 0)
     • Decrement frequency of 'u': frequencyDifference.put('u', -1)
     • frequencyDifference = {'g': 0, 'd': 0, 'a': 1, 'e': 0, 'r': 0, 's': 0, 'u': -1, 'i': -1, 'm': 1, 'n': -1, 'p': 1}
   • i = 10:
     • charT = 'n', charS = 's'
     • Increment frequency of 'n': frequencyDifference.put('n', 0)
     • Decrement frequency of 's': frequencyDifference.put('s', -1)
     • frequencyDifference = {'g': 0, 'd': 0, 'a': 1, 'e': 0, 'r': 0, 's': -1, 'u': -1, 'i': -1, 'm': 1, 'n': 0, 'p': 1}

3. Calculate steps:

   • Initialize steps = 0
   • Iterate over frequencyDifference values:
     • 'g' = 0 -> steps += 0
     • 'd' = 0 -> steps += 0
     • 'a' = 1 -> steps += 1
     • 'e' = 0 -> steps += 0
     • 'r' = 0 -> steps += 0
     • 's' = -1 -> steps += 0
     • 'u' = -1 -> steps += 0
     • 'i' = -1 -> steps += 0
     • 'm' = 1 -> steps += 1
     • 'n' = 0 -> steps += 0
     • 'p' = 1 -> steps += 1

4. Return result:

   • steps = 3

Thus, the minimum number of replacements needed to make "garumdespgn" an anagram of "designgurus" is 3.

Code

import java.util.HashMap;
import java.util.Map;

class Solution {

  public int calculateSteps(String s, String t) {
    Map<Character, Integer> frequencyDifference = new HashMap<>();

    // Count the difference in frequencies of characters between t and s
    for (int i = 0; i < s.length(); i++) {
      char charT = t.charAt(i);
      char charS = s.charAt(i);

      frequencyDifference.put(
        charT,
        frequencyDifference.getOrDefault(charT, 0) + 1
      );
      frequencyDifference.put(
        charS,
        frequencyDifference.getOrDefault(charS, 0) - 1
      );
    }

    int steps = 0;
    // Calculate the number of steps needed to make t an anagram of s
    for (int count : frequencyDifference.values()) {
      // Add the positive difference of character counts to steps
      // This represents the number of characters to be replaced
      if (count > 0) {
        steps += count;
      }
    }

    return steps;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.calculateSteps("designgurus", "garumdespgn")); // Output: 4
    System.out.println(sol.calculateSteps("abc", "def")); // Output: 3
    System.out.println(sol.calculateSteps("listen", "silent")); // Output: 0
  }
}

Complexity Analysis

Time Complexity

• The code performs a single loop over the length of the strings s and t, which is , where n is the length of the strings.
• The HashMap operations (put and get) are average .
• Therefore, the overall time complexity is .

Space Complexity

• The space complexity is determined by the HashMap, which stores at most 26 character frequencies, resulting in space complexity since the number of unique characters is constant.