Minimum Number of Steps to Make Two Strings Anagram

Medium
347.

Minimum Number of Steps to Make Two Strings Anagram

Minimum Number of Steps to Make Two Strings Anagram is a medium coding problem on strings, hash table and counting, asked in Amazon, Microsoft, Adobe and Twitter interviews.

You are given two strings s and t of the same length. In one step you may replace any character of t with any other character.

Return the minimum number of steps needed to make t an anagram of s.

Example 1

Input
s = "bab", t = "aba"
Output
1
Explanation
Replacing the first a of t with b gives "bba", an anagram of "bab".

Example 2

Input
s = "leetcode", t = "practice"
Output
5

Example 3

Input
s = "anagram", t = "mangaar"
Output
0

Constraints

  • 1 <= s.length <= 40
  • t.length == s.length
  • Both consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var minSteps = function(s, t) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Steps to Make Two Strings Anagram Solution

Minimum Number of Steps to Make Two Strings Anagram solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Steps to Make Two Strings Anagram is a medium coding problem on strings, hash table and counting, asked in Amazon, Microsoft, Adobe and Twitter interviews.

Problem statement

You are given two strings s and t of the same length. In one step you may replace any character of t with any other character.

Return the minimum number of steps needed to make t an anagram of s.

Example 1

Input: s = "bab", t = "aba"
Output: 1
Explanation: Replacing the first a of t with b gives "bba", an anagram of "bab".

Example 2

Input: s = "leetcode", t = "practice"
Output: 5

Example 3

Input: s = "anagram", t = "mangaar"
Output: 0

Constraints

  • 1 <= s.length <= 40
  • t.length == s.length
  • Both consist of lowercase English letters.

Hints for Minimum Number of Steps to Make Two Strings Anagram

  1. Hint 1

    Count each letter in both strings and look at the difference.

  2. Hint 2

    Every letter s needs more of has to be written into t somewhere — one step each.

  3. Hint 3

    Because the lengths match, the surplus in t exactly covers those slots, so summing the positive differences is the answer.

How to solve Minimum Number of Steps to Make Two Strings Anagram

Count each letter in s minus its count in t; the sum of the positive differences is how many characters t must change.

Approach

  1. Add 1 per letter of s, subtract 1 per letter of t in a 26-slot array.
  2. Sum the positive entries.

Why it works

Each letter s has more of must be written into t by one replacement, and because the lengths are equal the surplus letters in t supply exactly that many slots.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Summing absolute differences double-counts; positive (or negative) side only.

Reference solution

Python

def minSteps(s: str, t: str) -> int:
    count = [0] * 26
    for ch in s:
        count[ord(ch) - 97] += 1
    for ch in t:
        count[ord(ch) - 97] -= 1
    return sum(c for c in count if c > 0)

Java

public static int minSteps(String s, String t) {
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) count[s.charAt(i) - 'a']++;
    for (int i = 0; i < t.length(); i++) count[t.charAt(i) - 'a']--;
    int steps = 0;
    for (int c = 0; c < 26; c++) {
        if (count[c] > 0) steps += count[c];
    }
    return steps;
}

C++

int minSteps(string s, string t) {
    vector<int> count(26, 0);
    for (char ch : s) count[ch - 'a']++;
    for (char ch : t) count[ch - 'a']--;
    int steps = 0;
    for (int c = 0; c < 26; c++) {
        if (count[c] > 0) steps += count[c];
    }
    return steps;
}

JavaScript

var minSteps = function(s, t) {
    const count = new Array(26).fill(0);
    for (let i = 0; i < s.length; i++) count[s.charCodeAt(i) - 97]++;
    for (let i = 0; i < t.length; i++) count[t.charCodeAt(i) - 97]--;
    let steps = 0;
    for (let c = 0; c < 26; c++) {
        if (count[c] > 0) steps += count[c];
    }
    return steps;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets