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 makes andt anagrams of each other.

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

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3

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 * 10^5
  • s and t consist of lowercase English letters.

Solution

Method 1 – Counting Character Differences

Intuition

To make s and t anagrams, we need to match the character counts. For each character, the difference in counts must be appended to one string or the other. The sum of absolute differences gives the minimum steps.

Approach

  1. Count frequency of each character in s and t.
  2. For each character, add the absolute difference in counts to the answer.
  3. The total is the minimum steps needed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    int minSteps(string s, string t) {
        vector<int> cs(26, 0), ct(26, 0);
        for (char c : s) cs[c - 'a']++;
        for (char c : t) ct[c - 'a']++;
        int res = 0;
        for (int i = 0; i < 26; ++i) res += abs(cs[i] - ct[i]);
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func minSteps(s, t string) int {
    cs, ct := make([]int, 26), make([]int, 26)
    for _, c := range s {
        cs[c-'a']++
    }
    for _, c := range t {
        ct[c-'a']++
    }
    res := 0
    for i := 0; i < 26; i++ {
        if cs[i] > ct[i] {
            res += cs[i] - ct[i]
        } else {
            res += ct[i] - cs[i]
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int minSteps(String s, String t) {
        int[] cs = new int[26], ct = new int[26];
        for (char c : s.toCharArray()) cs[c - 'a']++;
        for (char c : t.toCharArray()) ct[c - 'a']++;
        int res = 0;
        for (int i = 0; i < 26; ++i) res += Math.abs(cs[i] - ct[i]);
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun minSteps(s: String, t: String): Int {
        val cs = IntArray(26)
        val ct = IntArray(26)
        for (c in s) cs[c - 'a']++
        for (c in t) ct[c - 'a']++
        var res = 0
        for (i in 0..25) res += kotlin.math.abs(cs[i] - ct[i])
        return res
    }
}
1
2
3
4
5

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        from collections import Counter
        cs, ct = Counter(s), Counter(t)
        return sum(abs(cs[c] - ct[c]) for c in set(cs) | set(ct))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

use std::collections::HashMap;
impl Solution {
    pub fn min_steps(s: String, t: String) -> i32 {
        let mut cs = [0; 26];
        let mut ct = [0; 26];
        for c in s.chars() { cs[(c as u8 - b'a') as usize] += 1; }
        for c in t.chars() { ct[(c as u8 - b'a') as usize] += 1; }
        (0..26).map(|i| (cs[i] - ct[i]).abs()).sum()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    minSteps(s: string, t: string): number {
        const cs = Array(26).fill(0), ct = Array(26).fill(0);
        for (const c of s) cs[c.charCodeAt(0) - 97]++;
        for (const c of t) ct[c.charCodeAt(0) - 97]++;
        let res = 0;
        for (let i = 0; i < 26; ++i) res += Math.abs(cs[i] - ct[i]);
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — n = length of s + t, single pass for counts.
  • 🧺 Space complexity: O(1) — constant extra space.