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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Steps to Make Two Strings Anagram

Difficulty: Medium

Problem Description

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.

Key Insights

  • An anagram requires the same character counts for both strings.
  • The difference in character counts between the two strings determines the number of replacements needed.
  • Using a frequency count (hash table) allows us to efficiently calculate the required changes.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the strings. Space Complexity: O(1) because the character set (lowercase English letters) is fixed.

Solution

To solve this problem, we can use a frequency count for both strings s and t. We will create two arrays of size 26 (for each letter in the alphabet) to count occurrences of each character in both strings. Then, we will calculate the number of steps required by comparing the counts. The number of steps needed to make t an anagram of s is the sum of the positive differences between the counts of each character.

Code Solutions

def min_steps_to_anagram(s: str, t: str) -> int:
    # Frequency arrays for each character in the alphabet
    count_s = [0] * 26
    count_t = [0] * 26

    # Fill frequency counts for both strings
    for char in s:
        count_s[ord(char) - ord('a')] += 1
    for char in t:
        count_t[ord(char) - ord('a')] += 1

    # Calculate the number of steps needed
    steps = 0
    for i in range(26):
        if count_s[i] > count_t[i]:
            steps += count_s[i] - count_t[i]

    return steps
← Back to All Questions