Minimum Number of Steps to Make Two Strings Anagram solution and explanation
Google
9 more videos on this problem
Leetcode 1347. Minimum Number of Steps to Make Two Strings AnagramFraz · 6:40 · 11K views
Minimum Number of Steps to Make Two Strings Anagram | Simple | Intuitive | Google | Leetcode 1347codestorywithMIK · 19:24 · 6K views
#Leetcode 1347. Minimum Number of Steps to Make Two Strings AnagramEngineering Digest · 7:19 · 2K views
1347. Minimum Number of Steps to Make Two Strings Anagram | ArraysAryan Mittal · 7:54 · 2K views
Leetcode Solution - 1347 Minimum Number of Steps to Make Two Strings AnagramJohn Leonardo · 5:57 · 2K views
Leetcode | 1347. Minimum Number of Steps to Make Two Strings Anagram | Medium | Java SolutionDeveloper Docs · 5:59 · 674 views
Minimum Number of Steps to Make Two Strings Anagram - LeetCode #1347 with python programmingCodingNinja · 8:34 · 624 views
Minimum Number of Steps to Make Two Strings Anagram | 1347 Leetcode | Python3CodeMeThere · 4:11 · 345 views
Minimum Number of Steps to Make Two Strings Anagram (Leetcode 1347)Coding Interviews · 11:09 · 340 views
Leetcode Medium: 1347 Minimum Number of Steps to Make Two Strings Anagramleetcode · 6:24 · 322 views
The 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 * 104s.length == t.lengthsandtconsist of lowercase English letters only.
Approach overview
Problem Overview: You are given two strings s and t of the same length. In one step you can replace any character in t. The goal is to compute the minimum number of replacements required so that t becomes an anagram of s.
Approach 1: Sorting and Compare (O(n log n) time, O(n) space)
A straightforward way to reason about anagrams is sorting both strings. If two strings are anagrams, their sorted versions are identical. Sort s and t, then iterate through both arrays and count mismatched characters. Each mismatch indicates a character in t that must be replaced. Sorting dominates the runtime at O(n log n), while storing sorted arrays requires O(n) space. This approach works but wastes time doing full ordering when the problem only requires frequency comparison.
Approach 2: Frequency Count Method (O(n) time, O(1) space)
The optimal solution relies on counting character frequencies using a fixed-size array or hash map. Iterate through string s and increment counts for each character. Then iterate through t and decrement the corresponding counts. If a count becomes negative, it means t has more of that character than s, so a replacement is required. Increment the step counter in that case. Because the alphabet size is constant (26 lowercase letters), the frequency structure uses constant space. The entire algorithm runs in O(n) time with O(1) space.
This technique is common in problems involving anagrams or character balancing. The idea is to track the difference between character distributions rather than reconstructing the actual anagram. A simple integer array indexed by char - 'a' works well, though a hash table also works if the character set is larger.
Conceptually, you are computing how many characters in t exceed the available counts from s. Every extra occurrence forces a replacement. This makes the solution a classic counting pattern combined with efficient string traversal.
Recommended for interviews: The frequency count method. Interviewers expect you to recognize that anagrams depend only on character counts, not order. Mentioning a sorting approach first demonstrates baseline reasoning, but moving to the O(n) counting solution shows stronger algorithmic intuition and understanding of constant-space optimizations.
Approach 1: Frequency Count Method
In this method, we need to count the frequency of each character in strings s and t. We then calculate the number of changes required in t by comparing these frequencies. Specifically, for each character, if the frequency count in s is greater than in t, those are the extra characters needed in t. The total number of these extra characters across all characters gives the result.
def minSteps(s: str, t: str) -> int:
count = [0] * 26
steps = 0
for c in s:
count[ord(c) - ord('a')] += 1
for c in t:
count[ord(c) - ord('a')] -= 1
for freq in count:
if freq > 0:
steps += freq
return steps
print(minSteps("leetcode", "practice"))public class Solution {
public int minSteps(String s, String t) {
int[] count = new int[26];
int steps = 0;
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
for (char c : t.toCharArray()) {
count[c - 'a']--;
}
for (int freq : count) {
if (freq > 0) {
steps += freq;
}
}
return steps;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minSteps("leetcode", "practice"));
}
}#include <iostream>
#include <vector>
int minSteps(std::string s, std::string t) {
std::vector<int> count(26, 0);
int steps = 0;
for (char c : s) {
count[c - 'a']++;
}
for (char c : t) {
count[c - 'a']--;
}
for (int freq : count) {
if (freq > 0) {
steps += freq;
}
}
return steps;
}
int main() {
std::string s = "leetcode";
std::string t = "practice";
std::cout << minSteps(s, t);
return 0;
}function minSteps(s, t) {
let count = new Array(26).fill(0);
let steps = 0;
for (let char of s) {
count[char.charCodeAt(0) - 97]++;
}
for (let char of t) {
count[char.charCodeAt(0) - 97]--;
}
for (let freq of count) {
if (freq > 0) {
steps += freq;
}
}
return steps;
}
console.log(minSteps("leetcode", "practice"));#include <stdio.h>
#include <string.h>
int minSteps(char * s, char * t) {
int count[26] = {0};
int steps = 0;
// Count frequency of each character in s
for (int i = 0; s[i] != '\0'; i++) {
count[s[i] - 'a']++;
}
// Decrease the frequency according to characters in t
for (int i = 0; t[i] != '\0'; i++) {
count[t[i] - 'a']--;
}
// Count the number of steps required
for (int i = 0; i < 26; i++) {
if (count[i] > 0) {
steps += count[i];
}
}
return steps;
}
int main() {
char s[] = "leetcode";
char t[] = "practice";
printf("%d", minSteps(s, t));
return 0;
}using System;
class Solution {
public int MinSteps(string s, string t) {
int[] count = new int[26];
int steps = 0;
foreach (char c in s) {
count[c - 'a']++;
}
foreach (char c in t) {
count[c - 'a']--;
}
foreach (int freq in count) {
if (freq > 0) {
steps += freq;
}
}
return steps;
}
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.MinSteps("leetcode", "practice"));
}
}The Python function achieves the solution using a list to hold frequency counts. Characters in s increment counters, while those in t decrement, with a final loop to tally required changes.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Counting
We can use a hash table or an array cnt to count the occurrences of each character in the string s. Then, we traverse the string t. For each character, we decrement its count in cnt. If the decremented value is less than 0, it means that this character appears more times in the string t than in the string s. In this case, we need to replace this character and increment the answer by one.
After the traversal, we return the answer.
The time complexity is O(m + n), and the space complexity is O(|\Sigma|), where m and n are the lengths of the strings s and t, respectively, and |\Sigma| is the size of the character set. In this problem, the character set consists of lowercase letters, so |\Sigma| = 26.
function minSteps(s: string, t: string): number {
const cnt: number[] = Array(26).fill(0);
for (const c of s) {
++cnt[c.charCodeAt(0) - 97];
}
let ans = 0;
for (const c of t) {
if (--cnt[c.charCodeAt(0) - 97] < 0) {
++ans;
}
}
return ans;
}func minSteps(s string, t string) (ans int) {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
for _, c := range t {
cnt[c-'a']--
if cnt[c-'a'] < 0 {
ans++
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Frequency Count Method | Time Complexity: O(n) |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting Both Strings | O(n log n) | O(n) | Simple conceptual solution when constraints are small or when sorting utilities are already used. |
| Frequency Count (Hash Table / Array) | O(n) | O(1) | Optimal approach for large strings. Best for interview settings and production code. |
Frequently asked questions
Is Minimum Number of Steps to Make Two Strings Anagram easy or hard?
The problem is rated Medium because the key insight is recognizing that only frequency differences matter. Once you map characters to counts, the implementation becomes straightforward and runs in linear time.
Minimum Number of Steps to Make Two Strings Anagram Python/Java solution
Both Python and Java implementations follow the same idea: maintain a frequency array for characters in s, then iterate through t and reduce counts while counting excess characters. Python typically uses a list of size 26, while Java uses an int[26] array for constant-time updates.
How to solve Minimum Number of Steps to Make Two Strings Anagram in O(n)?
Create an integer array of size 26 to store character frequencies from string s. Iterate through s and increment counts. Then iterate through t and decrement counts; if a count becomes negative, increment the step counter because that character must be replaced. The traversal of both strings makes the algorithm O(n).
What is the best approach for Minimum Number of Steps to Make Two Strings Anagram?
The best approach uses frequency counting. Count characters in string s, then traverse string t and reduce those counts. Whenever a character in t exceeds the available count from s, you must replace it, so increment the step counter. This runs in O(n) time with O(1) space when using a fixed 26-length array.
Is Minimum Number of Steps to Make Two Strings Anagram asked at Google/Amazon/Meta?
Anagram and frequency-counting problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem test your understanding of hash maps, character counting, and linear-time string processing.
What data structure is used in Minimum Number of Steps to Make Two Strings Anagram?
The primary data structure is a frequency table, typically implemented as a fixed-size array of length 26 for lowercase letters. A hash map can also be used for more general character sets. The structure tracks the difference between character counts in the two strings.
What is the time complexity of Minimum Number of Steps to Make Two Strings Anagram?
The optimal solution runs in O(n) time where n is the string length. Each character of both strings is processed once using a frequency array. Space complexity is O(1) because the alphabet size (26 lowercase letters) is constant.