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

Number: 1469

Difficulty: Medium

Paid? No

Companies: Bloomberg, DoorDash, IXL, Amazon, Oracle, Adobe, Apple, Google, X

Problem Description

Given two strings s and t of the same length, determine the minimum number of steps required to make t an anagram of s. In one step, you can choose any character in t and replace it with any other character. An anagram of a string is a rearrangement of its characters.

Key Insights

  • Count the frequency of each character in both s and t.
  • Calculate the difference for each character where s has a higher frequency than t.
  • The sum of these positive differences is the minimum number of steps needed.
  • Focus only on characters where t is deficient; extra occurrences in t do not help.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the strings, as we iterate through both strings. Space Complexity: O(1) since the frequency counters have a fixed size of 26 (for lowercase English letters).

Solution

The solution uses fixed-size arrays or hash tables to count the frequency of each letter in both strings. By iterating over both strings, we fill these frequency counters. We then calculate, for each character, how many more times it appears in s compared to t. The sum of these differences gives the minimum number of modifications (steps) required to convert t into an anagram of s. This approach efficiently leverages counting and simple arithmetic to achieve the desired result.

Code Solutions

def minSteps(s: str, t: str) -> int:
    # Initialize frequency arrays for 26 lowercase letters for both strings
    count_s = [0] * 26
    count_t = [0] * 26
    
    # Count frequency of each character in s
    for char in s:
        count_s[ord(char) - ord('a')] += 1
        
    # Count frequency of each character in t
    for char in t:
        count_t[ord(char) - ord('a')] += 1
        
    steps = 0
    # For each letter, if s requires more instances than present in t,
    # add the deficit to steps
    for i in range(26):
        if count_s[i] > count_t[i]:
            steps += count_s[i] - count_t[i]
            
    return steps

# Example usage:
print(minSteps("bab", "aba"))  # Output: 1
← Back to All Questions