# Minimum Number of Steps to Make Two Strings Anagram
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-steps-to-make-two-strings-anagram
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [SoFi](https://scaleengineer.com/companies/sofi), [X](https://scaleengineer.com/companies/x), [IXL](https://scaleengineer.com/companies/ixl)
---
## Problem
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.

# Approaches
## Frequency Counting with a Hash Map
This approach involves using a hash map to store the character frequencies of the target anagram string `s`. We then iterate through the string `t` and 'use up' the characters that match. The total count of characters remaining in the map represents the number of characters in `s` that were not present in `t`, which is exactly the number of replacements needed.
**Time:** O(N), where N is the length of the strings. We iterate through `s` once (O(N)), `t` once (O(N)), and the map's values once (O(K), where K <= 26). The total is O(N). · **Space:** O(K), where K is the number of unique characters in the alphabet. For lowercase English letters, K is at most 26, so the space is O(1).
**Pros:** Conceptually simple and easy to implement.; Flexible enough to work with any character set, not just lowercase English letters.
**Cons:** Slightly less performant than an array-based approach due to the overhead of hash map operations (hashing, collision handling).
### Explanation
To solve this problem, we first need to know the character composition of an anagram of `s`. We can achieve this by counting the frequency of each character in `s` and storing it in a hash map.

Once we have the frequency map for `s`, we can iterate through string `t`. For each character in `t`, we check if it's a character that `s` needs. If it is (i.e., it's in our map with a count greater than zero), we decrement its count in the map. This signifies that one character from `t` has successfully matched one required character for the anagram.

After checking all characters in `t`, the hash map will contain the counts of characters that are in `s` but were not matched by characters from `t`. The sum of these leftover counts gives the total number of characters that are 'missing' from `t`. Since each replacement operation can fix one missing character, this sum is the minimum number of steps required.

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

class Solution {
    public int minSteps(String s, String t) {
        Map<Character, Integer> sCounts = new HashMap<>();
        for (char c : s.toCharArray()) {
            sCounts.put(c, sCounts.getOrDefault(c, 0) + 1);
        }

        // Decrement counts for characters present in t
        for (char c : t.toCharArray()) {
            if (sCounts.containsKey(c) && sCounts.get(c) > 0) {
                sCounts.put(c, sCounts.get(c) - 1);
            }
        }

        // Sum of remaining counts is the number of characters to change
        int steps = 0;
        for (int count : sCounts.values()) {
            steps += count;
        }

        return steps;
    }
}
```
### Algorithm
*   Create a frequency map for all characters in string `s` using a Hash Map.
*   Iterate through string `t`. For each character, if it's in the frequency map and its count is positive, decrement the count.
*   The result is the sum of all remaining counts in the frequency map.

## Optimized Frequency Counting with an Array
This approach improves upon the hash map method by using a simple array of size 26 as a frequency counter, which is possible because the input strings consist only of lowercase English letters. We calculate the net difference in character frequencies between `s` and `t`. The number of required changes is the sum of all characters that `s` has in excess compared to `t`.
**Time:** O(N), where N is the length of the strings. We iterate through the strings to populate the frequency array (O(N)) and then iterate through the array of size 26 (O(1)). The total complexity is O(N). · **Space:** O(1), as the space used is a fixed-size array of 26 integers, which does not depend on the input string length.
**Pros:** Extremely efficient in both time and space due to direct array indexing.; Simple to implement for a fixed, small character set.
**Cons:** The implementation is specific to the character set ('a'-'z') and would require changes for other character sets.
### Explanation
Given the constraint that strings only contain lowercase English letters, we can use a fixed-size array of 26 integers for frequency counting, which is more efficient than a hash map. Each index in the array corresponds to a letter from 'a' to 'z'.

The algorithm works by first populating this array with the character counts from string `s`. Then, it iterates through string `t` and decrements the counts for each character found. After these two passes, the array holds the difference in frequencies for each character between `s` and `t`. A positive value at `counts[i]` means `s` has more of character `('a' + i)` than `t`, while a negative value means `t` has more.

The minimum number of steps is the number of characters we need to introduce into `t` to match `s`. This is precisely the sum of all positive counts in our final frequency array. Each positive count `counts[i]` represents a deficit of that character in `t` that needs to be filled by a replacement.

```java
class Solution {
    public int minSteps(String s, String t) {
        int[] counts = new int[26];
        
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        
        for (char c : t.toCharArray()) {
            counts[c - 'a']--;
        }
        
        int steps = 0;
        for (int count : counts) {
            if (count > 0) {
                steps += count;
            }
        }
        
        return steps;
    }
}
```
As a small optimization, since the string lengths are equal, the loops for `s` and `t` can be combined into one:
```java
// Combined loop optimization
class Solution {
    public int minSteps(String s, String t) {
        int[] counts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - 'a']++;
            counts[t.charAt(i) - 'a']--;
        }
        
        int steps = 0;
        for (int count : counts) {
            if (count > 0) {
                steps += count;
            }
        }
        return steps;
    }
}
```
### Algorithm
*   Initialize an integer array `counts` of size 26 to all zeros.
*   Iterate through string `s`, incrementing the count for each character.
*   Iterate through string `t`, decrementing the count for each character.
*   Sum all the positive values in the `counts` array. This sum is the minimum number of steps.

# Solutions
### JavaScript

```javascript
/** * @param {string} s * @param {string} t * @return {number} */ var minSteps =
  function (s, t) {
    const cnt = new Array(26).fill(0);
    for (const c of s) {
      const i = c.charCodeAt(0) - " a ".charCodeAt(0);
      ++cnt[i];
    }
    let ans = 0;
    for (const c of t) {
      const i = c.charCodeAt(0) - " a ".charCodeAt(0);
      ans += --cnt[i] < 0;
    }
    return ans;
  };

```

### Java

```java
class Solution {
public
  int minSteps(String s, String t) {
    int[] cnt = new int[26];
    for (int i = 0; i < s.length(); ++i) {
      ++cnt[s.charAt(i) - 'a'];
    }
    int ans = 0;
    for (int i = 0; i < t.length(); ++i) {
      if (--cnt[t.charAt(i) - 'a'] < 0) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minSteps(string s, string t) {
    int cnt[26]{};
    for (char &c : s)
      ++cnt[c - 'a'];
    int ans = 0;
    for (char &c : t) {
      ans += --cnt[c - 'a'] < 0;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minSteps(self, s: str, t: str) -> int: cnt = Counter(s) ans = 0 for c in t: if cnt[c] > 0: cnt[c] -= 1 else: ans += 1 return ans

```