# Minimum Number of Steps to Make Two Strings Anagram II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-steps-to-make-two-strings-anagram-ii
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [Wealthfront](https://scaleengineer.com/companies/wealthfront)
---
## Problem
You are given two strings `s` and `t`. In one step, you can append **any character** to either `s` or `t`.

Return _the minimum number of steps to make_ `s` _and_ `t` _**anagrams** of each other._

An **anagram** of a string is a string that contains the same characters with a different (or the same) ordering.

**Example 1:**

**Input:** s = "**lee**tco**de**", t = "co**a**t**s**"
**Output:** 7
**Explanation:** 
- In 2 steps, we can append the letters in "as" onto s = "leetcode", forming s = "leetcode**as**".
- In 5 steps, we can append the letters in "leede" onto t = "coats", forming t = "coats**leede**".
"leetcodeas" and "coatsleede" are now anagrams of each other.
We used a total of 2 + 5 = 7 steps.
It can be shown that there is no way to make them anagrams of each other with less than 7 steps.

**Example 2:**

**Input:** s = "night", t = "thing"
**Output:** 0
**Explanation:** The given strings are already anagrams of each other. Thus, we do not need any further steps.

**Constraints:**

* `1 <= s.length, t.length <= 2 * 105`
* `s` and `t` consist of lowercase English letters.

# Approaches
## Using HashMaps to Count Frequencies
This approach uses two HashMaps to store the character frequencies for each string, `s` and `t`. We first iterate through both strings to populate their respective frequency maps. Then, we iterate through all possible lowercase English letters ('a' through 'z') and for each letter, we find the counts from both maps (defaulting to 0 if not present). The absolute difference between these counts represents the number of appends needed for that specific character. Summing these differences for all 26 letters gives the total minimum steps required.
**Time:** O(N + M), where N is the length of `s` and M is the length of `t`. We iterate through both strings once to build the maps (O(N + M)) and then iterate a constant number of times (26) to compare frequencies. Thus, the overall complexity is dominated by the string traversals. · **Space:** O(K), where K is the number of unique characters in the alphabet. Since the problem specifies lowercase English letters, K is at most 26, making the space complexity constant, O(1).
**Pros:** Conceptually straightforward and easy to implement.; Flexible and general; it would work for any character set, not just lowercase English letters.
**Cons:** Slightly less performant due to the overhead of hashing and `Map.Entry` object creation.; Uses more memory in practice compared to a simple array.
### Explanation
To make two strings anagrams, they must have the exact same character counts. The goal is to find the minimum number of appends to achieve this. This can be found by calculating the total number of characters that are mismatched between the two strings.

This method uses HashMaps, a common data structure for frequency counting, which maps each character to its count.

```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);
        }

        Map<Character, Integer> tCounts = new HashMap<>();
        for (char c : t.toCharArray()) {
            tCounts.put(c, tCounts.getOrDefault(c, 0) + 1);
        }

        int steps = 0;
        for (char c = 'a'; c <= 'z'; c++) {
            int sCount = sCounts.getOrDefault(c, 0);
            int tCount = tCounts.getOrDefault(c, 0);
            steps += Math.abs(sCount - tCount);
        }

        return steps;
    }
}
```

For any character `c`, if `s` has more `c`'s than `t`, we need to append `sCount - tCount` copies of `c` to `t`. Conversely, if `t` has more, we need to append `tCount - sCount` copies to `s`. In both cases, the number of appends for character `c` is `abs(sCount - tCount)`. Summing this over all characters gives the total steps.
### Algorithm
- Initialize two `HashMap`s, `sCounts` and `tCounts`, to store character frequencies for strings `s` and `t` respectively.
- Iterate through string `s`. For each character, increment its count in `sCounts`.
- Iterate through string `t`. For each character, increment its count in `tCounts`.
- Initialize a variable `steps` to 0.
- Loop through all 26 lowercase English letters from 'a' to 'z'.
- For each letter, get its frequency from `sCounts` and `tCounts`, using 0 as a default if the letter is not present.
- Calculate the absolute difference between the two frequencies and add it to `steps`.
- After checking all letters, `steps` will hold the total minimum number of appends required. Return `steps`.

## Optimized Single Array for Frequency Counting
A more efficient approach utilizes a single integer array of size 26 to track the net difference in character frequencies between the two strings. We first iterate through string `s`, incrementing the count for each character in the array. Then, we iterate through string `t`, decrementing the count for each character. After processing both strings, each element `count[i]` in the array represents the difference in frequency for the character `'a' + i`. The total number of steps is the sum of the absolute values of all elements in this array.
**Time:** O(N + M), where N is the length of `s` and M is the length of `t`. We perform a single pass over each string and one pass over the 26-element frequency array. This is the most efficient time complexity possible as we must look at every character at least once. · **Space:** O(1). We use a single integer array of a fixed size (26), which is constant space and does not depend on the input string lengths.
**Pros:** Highly efficient in both time and space due to direct array indexing and no object overhead.; Uses a single, compact data structure, making the code concise and fast.; Optimal solution for the given constraints.
**Cons:** This approach is specifically tailored to a known, small character set (lowercase English letters). It would need modification for larger character sets like Unicode.
### Explanation
Since the input strings are guaranteed to contain only lowercase English letters, we can use a simple array of size 26 as a frequency map instead of a HashMap. This is more performant due to direct memory access and avoids the overhead of hashing.

The core idea is to use a single array to represent the difference in character counts. We populate the array with counts from `s` and then subtract the counts from `t`. The final values in the array represent `count_s[char] - count_t[char]`. The total number of characters to be added is the sum of the absolute values of these differences.

```java
class Solution {
    public int minSteps(String s, String t) {
        int[] counts = new int[26];
        
        // Increment for characters in s
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        
        // Decrement for characters in t
        for (char c : t.toCharArray()) {
            counts[c - 'a']--;
        }
        
        int steps = 0;
        // Sum the absolute differences
        for (int count : counts) {
            steps += Math.abs(count);
        }
        
        return steps;
    }
}
```
For example, if `counts[0]` (for character 'a') is 2, it means `s` has two more 'a's than `t`, so we need to add two 'a's to `t`. If `counts[0]` is -3, `t` has three more 'a's, so we need to add three 'a's to `s`. In both cases, the number of steps for 'a' is `abs(counts[0])`.
### Algorithm
- Initialize an integer array `counts` of size 26 with all elements set to 0. This array will store the net frequency difference for each character.
- Iterate through each character `c` in string `s`. For each character, increment the corresponding counter in the array: `counts[c - 'a']++`.
- Iterate through each character `c` in string `t`. For each character, decrement the corresponding counter in the array: `counts[c - 'a']--`.
- After these two loops, `counts[i]` holds the value `(frequency of 'a'+i in s) - (frequency of 'a'+i in t)`.
- Initialize a variable `steps` to 0.
- Iterate through the `counts` array. For each element `count`, add its absolute value to `steps`.
- Return `steps`.

# Solutions
### Java

```java
class Solution {
public
  int minSteps(String s, String t) {
    int[] cnt = new int[26];
    for (char c : s.toCharArray()) {
      ++cnt[c - 'a'];
    }
    for (char c : t.toCharArray()) {
      --cnt[c - 'a'];
    }
    int ans = 0;
    for (int v : cnt) {
      ans += Math.abs(v);
    }
    return ans;
  }
}

```

### JavaScript

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

```

### CPP

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

```

### Python

```python
class Solution:
    def minSteps(self, s: str, t: str) -> int: cnt = Counter(s) for c in t: cnt[c] -= 1 return sum(abs(v) for v in cnt . values())

```