Minimum Number of Steps to Make Two Strings Anagram

Minimum Number of Steps to Make Two Strings Anagram - 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.

Input & Output

Example 1 — Basic Case

$ Input: s = "bab", t = "aba"

› Output: 1

💡 Note: String t has 2 'a's but s only has 1 'a'. Replace one 'a' in t with 'b' to make "bab" or "bba"

Example 2 — Multiple Changes

$ Input: s = "leetcode", t = "practice"

› Output: 5

💡 Note: t needs to be transformed: 'p'→'l', 'r'→'e', 'a'→'e', 'i'→'t', 'c' remains, so 5 changes needed

Example 3 — Already Anagram

$ Input: s = "anagram", t = "mangaar"

› Output: 0

💡 Note: Both strings already have same character frequencies, no changes needed

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s.length == t.length
s and t consist of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Two equal-length strings s and t

Frequency Count

Count character occurrences in both strings

Calculate Steps

Count excess characters in t that need replacement

Key Takeaway

🎯 Key Insight: Count excess characters in t compared to s - those are the minimum replacements needed

Asked in

f Facebook 15 a Amazon 12 M Microsoft 8

The key insight is to count character frequencies in both strings and find excess characters in t that need replacement. Best approach uses single-pass frequency counting with O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Optimized	O(n)	O(1)	Count frequencies in single pass and calculate steps simultaneously
Character-by-Character Comparison	O(n)	O(1)	Compare each character position and count mismatches
Character Frequency Counting	O(n)	O(1)	Count character frequencies and calculate excess characters in t

Single Pass Optimized — Algorithm Steps

Step 1: Use single frequency array for both strings
Step 2: Increment count for each character in s
Step 3: Decrement count for each character in t
Step 4: Sum positive differences (excess in t)

Visualization

Tap to expand

Step-by-Step Walkthrough

Combined Count

Increment for s[i], decrement for t[i] in same loop

Identify Negatives

Negative values show excess characters in t

Sum Absolute

Sum absolute values of negative counts

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int solution(char* s, char* t) {
    // Use array for lowercase letters (a-z)
    int count[26] = {0};
    
    int len = strlen(s);
    
    // Count characters: +1 for s, -1 for t
    for (int i = 0; i < len; i++) {
        count[s[i] - 'a']++;
        count[t[i] - 'a']--;
    }
    
    // Count how many characters t has in excess
    int steps = 0;
    for (int i = 0; i < 26; i++) {
        if (count[i] < 0) {  // t has more of this character than s
            steps += abs(count[i]);
        }
    }
    
    return steps;
}

int main() {
    char s[100001], t[100001];
    fgets(s, sizeof(s), stdin);
    fgets(t, sizeof(t), stdin);
    
    // Remove newlines
    s[strcspn(s, "\n")] = 0;
    t[strcspn(t, "\n")] = 0;
    
    int result = solution(s, t);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through both strings of length n

✓ Linear Growth

Space Complexity

O(1)

Fixed size array for 26 lowercase letters

✓ Linear Space

89.4K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Optimized — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler