We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Steps to Make Two Strings Anagram II

Number: 2293

Difficulty: Medium

Paid? No

Companies: Wealthfront

Problem Description

Given two strings s and t, determine the minimum number of steps required to make the two strings anagrams of each other by appending any character to either string. An anagram is a permutation of characters of a string. Each step allows appending exactly one character.

Key Insights

  • Count the frequency of each character in both strings.
  • The number of required steps for a character is the absolute difference between its counts in the two strings.
  • Summing these differences over all characters gives the total number of insertions needed to balance the frequencies.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of s and m is the length of t, due to traversing each string once. Space Complexity: O(1), since the frequency map size is limited by the fixed alphabet (26 lowercase letters).

Solution

We use two hash tables (or dictionaries) to count the frequency of each character in s and t. For every character in the alphabet, we compute the absolute difference between the counts in s and t. The sum of these differences is the minimum number of steps required because it represents the imbalance of characters between the two strings. This approach leverages the fact that the alphabet is limited to lowercase English letters, ensuring constant space usage relative to the input size.

Code Solutions

# Define a function to calculate the minimum number of steps
def min_steps_to_make_anagram(s: str, t: str) -> int:
    # Initialize frequency dictionaries for both strings
    frequency_s = {}
    frequency_t = {}
    
    # Count each character in s
    for char in s:
        frequency_s[char] = frequency_s.get(char, 0) + 1
    
    # Count each character in t
    for char in t:
        frequency_t[char] = frequency_t.get(char, 0) + 1
    
    steps = 0
    # Iterate over each character in the alphabet (a to z)
    for char in "abcdefghijklmnopqrstuvwxyz":
        # Compute the absolute difference of counts in s and t
        count_s = frequency_s.get(char, 0)
        count_t = frequency_t.get(char, 0)
        steps += abs(count_s - count_t)
    
    return steps

# Example usage:
s = "leetcode"
t = "coats"
print(min_steps_to_make_anagram(s, t))  # Output: 7
← Back to All Questions