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.
- Difficulty: Medium
- Topics: Strings, Hash Table, Counting
- Asked at: Amazon, Microsoft, Adobe, Twitter
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 40t.length == s.lengthBoth consist of lowercase English letters.
Hints for Minimum Number of Steps to Make Two Strings Anagram
Hint 1
Count each letter in both strings and look at the difference.
Hint 2
Every letter
sneeds more of has to be written intotsomewhere — one step each.Hint 3
Because the lengths match, the surplus in
texactly 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
- Add 1 per letter of
s, subtract 1 per letter oftin a 26-slot array. - 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