{x}
blog image

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.

Solution Explanation: Minimum Steps to Make Two Strings Anagram

This problem asks for the minimum number of steps needed to transform string t into an anagram of string s by replacing characters in t. The core idea is to count character frequencies and find the discrepancies.

Approach:

  1. Character Counting: We use a frequency counter (hash table or array) to store the counts of each character (a-z) in string s. This allows for O(1) lookup of character counts.

  2. Comparison and Replacement: We iterate through string t. For each character in t:

    • We decrement its count in our frequency counter.
    • If the count becomes negative, it means we have more of that character in t than in s. Therefore, we need to replace this extra character, incrementing our ans (the minimum steps).

  3. Return the Minimum Steps: After processing all characters in t, ans holds the total number of replacements needed, which represents the minimum steps.

Time Complexity Analysis:

  • Creating the frequency counter for s: O(m), where m is the length of s.
  • Iterating through t and updating the counter: O(n), where n is the length of t.
  • Since m = n (given that s and t have the same length), the overall time complexity is O(n).

Space Complexity Analysis:

  • We use a frequency counter of size 26 (for lowercase English letters). This space is constant and does not depend on the input size.
  • Therefore, the space complexity is O(1).

Code Examples (Python, Java, C++, Go, TypeScript, Javascript):

The provided code snippets in multiple languages follow the algorithm described above. They all achieve O(n) time and O(1) space complexity. The differences lie primarily in syntax and data structure implementations (using Counter in Python, arrays in Java/C++/Go, and arrays in TypeScript/Javascript). Each example showcases the efficiency of this approach. The core logic remains consistent: count characters in s, iterate through t, and track replacements based on negative counts.