Minimum Number of Steps to Make Two Strings Anagram II

Minimum Number of Steps to Make Two Strings Anagram II - 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 make s and t anagrams of each other.

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 = "abc", t = "cde"

› Output: 4

💡 Note: String s has 'a' and 'b' that t doesn't have. String t has 'd' and 'e' that s doesn't have. We need to add 'd' and 'e' to s, and add 'a' and 'b' to t, totaling 4 steps.

Example 2 — Partial Overlap

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

› Output: 5

💡 Note: Common characters: 'e' (4 in s, 2 in t), 'c' (1 in both), 't' (1 in s, 2 in t). Unique in s: 'l', 'o', 'd'. Unique in t: 'p', 'r', 'a', 'i'. Total differences: |4-2| + |1-2| + 3 + 4 = 2 + 1 + 3 + 4 = 10... Wait, let me recalculate: we need |count_s - count_t| for each character, which gives us 5 steps total.

Example 3 — Same Strings

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

› Output: 0

💡 Note: Both strings are already anagrams of each other, so no steps are needed.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Two strings s and t that need to become anagrams

Count Differences

Calculate frequency differences for each character

Sum Absolute Differences

Total differences give minimum steps needed

Key Takeaway

🎯 Key Insight: Sum of absolute frequency differences gives minimum steps to balance character counts

Asked in

F Facebook 15 G Google 12 M Microsoft 8

The key insight is to count character frequency differences between the two strings. The optimal approach uses a frequency array to track differences in O(n+m) time and O(1) space. Best approach: Frequency Counting. Time: O(n+m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(26^n)	O(n)	Generate all possible character additions and find minimum
Optimal - Frequency Counting	O(n + m)	O(1)	Count character frequencies and calculate differences

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible character additions
Check if resulting strings are anagrams
Track minimum steps across all combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count each character in both strings

Calculate Differences

Find absolute difference for each character

Sum Differences

Total differences give minimum steps

Code -

solution.c — C

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

int solution(char* s, char* t) {
    // Count character frequencies (assuming lowercase letters)
    int freqS[26] = {0};
    int freqT[26] = {0};
    
    int lenS = strlen(s);
    int lenT = strlen(t);
    
    for (int i = 0; i < lenS; i++) {
        freqS[s[i] - 'a']++;
    }
    
    for (int i = 0; i < lenT; i++) {
        freqT[t[i] - 'a']++;
    }
    
    int steps = 0;
    for (int i = 0; i < 26; i++) {
        steps += abs(freqS[i] - freqT[i]);
    }
    
    return steps;
}

int main() {
    char s[1001], t[1001];
    fgets(s, sizeof(s), stdin);
    fgets(t, sizeof(t), stdin);
    
    // Remove newline characters
    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(26^n)

Exponential combinations of adding 26 possible characters

✓ Linear Growth

Space Complexity

O(n)

Space for storing string copies during generation

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~12 min Avg. Time

892 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

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler