Jobs

Interviews

Discussions

Minimum Number of Steps to Make Two Strings Anagram II

Medium

Asked by:

16 views

Topics:

ArraysStrings

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.

Example 1:

Input: s = "leetcode", t = "coats"
Output: 7
Explanation: 
- In 2 steps, we can append the letters in "as" onto s = "leetcode", forming s = "leetcodeas".
- In 5 steps, we can append the letters in "leede" onto t = "coats", forming t = "coatsleede".
"leetcodeas" and "coatsleede" are now anagrams of each other.
We used a total of 2 + 5 = 7 steps.
It can be shown that there is no way to make them anagrams of each other with less than 7 steps.

Example 2:

Input: s = "night", t = "thing"
Output: 0
Explanation: The given strings are already anagrams of each other. Thus, we do not need any further steps.

Constraints:

1 <= s.length, t.length <= 2 * 10⁵
s and t consist of lowercase English letters.

Try coding it in LeetCode

Minimum Number of Steps to Make Two Strings Anagram II

Medium

Asked by:

16 views

Topics:

ArraysStrings

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.

Example 1:

Input: s = "leetcode", t = "coats"
Output: 7
Explanation: 
- In 2 steps, we can append the letters in "as" onto s = "leetcode", forming s = "leetcodeas".
- In 5 steps, we can append the letters in "leede" onto t = "coats", forming t = "coatsleede".
"leetcodeas" and "coatsleede" are now anagrams of each other.
We used a total of 2 + 5 = 7 steps.
It can be shown that there is no way to make them anagrams of each other with less than 7 steps.

Example 2:

Input: s = "night", t = "thing"
Output: 0
Explanation: The given strings are already anagrams of each other. Thus, we do not need any further steps.

Constraints:

1 <= s.length, t.length <= 2 * 10⁵
s and t consist of lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the input strings `s` and `t` guaranteed to be non-empty?
Are the input strings composed only of lowercase English letters, or can they contain uppercase letters, numbers, or special characters?
If `s` and `t` have different lengths, what is the expected behavior?
Can the input strings contain Unicode characters, or should I assume ASCII only?
Are there any implicit constraints on the maximum length of the strings `s` and `t`?

Brute Force Solution

Approach

The brute force approach to finding the minimum number of steps to make two strings anagrams involves systematically checking every possible way to transform one string into an anagram of the other by adding or removing characters. We'll consider every character in the first string and try to match it with a character in the second string, and vice-versa.

Here's how the algorithm would work step-by-step:

Think about each character in the first string.
For each character in the first string, consider if it exists in the second string.
If a character from the first string is found in the second string, we can think of that as a match, and we don't need to change it.
If a character from the first string is NOT found in the second string, we'll need to change it (either by adding it to the second string or removing it from the first).
Now, do the same for each character in the second string, checking if it exists in the first string.
If a character from the second string is NOT found in the first string, it also needs to be changed.
Count up all the characters that didn't have a match in the other string.
The total count of these unmatched characters represents the minimum number of changes needed.

Code Implementation

def minSteps(string_one, string_two):
    unmatched_characters_count = 0
    
    # We need a mutable copy of string_two to remove characters as we find matches
    mutable_string_two = list(string_two)
    
    # Iterate through each character in the first string to find matches in the second
    for character_one in string_one:
        found_match_in_string_two = False
        for index_two in range(len(mutable_string_two)):
            if character_one == mutable_string_two[index_two]:
                # Once a match is found, remove it from the second string's mutable copy
                mutable_string_two.pop(index_two)
                found_match_in_string_two = True
                break
        if not found_match_in_string_two:
            # If a character from string_one is not found in string_two, it needs changing
            unmatched_characters_count += 1
            
    # Any remaining characters in mutable_string_two are also unmatched and need changing
    unmatched_characters_count += len(mutable_string_two)
    
    return unmatched_characters_count

Big(O) Analysis

Time Complexity

O(n) – The approach involves iterating through each character of the first string (let's say length n) and then iterating through each character of the second string (also length n) to find matches. This comparison for each character in the first string against the second string takes on average O(n) time. Doing this for all n characters in the first string results in an O(n*n) operation. However, a more efficient implementation of this strategy would use frequency maps (like hash tables or arrays of size 26 for lowercase English alphabets). Building these maps takes O(n) and O(m) time respectively (where n and m are the lengths of the strings). Comparing the frequency maps takes O(alphabet_size) which is constant. Therefore, the dominant factor is the initial traversal to build the frequency maps, resulting in O(n) or O(n+m) time complexity.

Space Complexity

O(1) – The provided plain English explanation describes a process of counting unmatched characters. This can be implemented using a fixed number of counters (e.g., an array of size 26 for lowercase English alphabets) regardless of the input string lengths. Therefore, the auxiliary space used is constant and does not depend on the input size N, leading to O(1) space complexity.

Optimal Solution

Approach

To find the minimum steps to make two strings anagrams, we can count the occurrences of each character in both strings and determine how many characters need to be changed. The key is to focus on the differences in character counts.

Here's how the algorithm would work step-by-step:

Imagine you have two bags of letter tiles, one for each string.
Go through the first bag and count how many of each type of letter you have. For example, count all the 'a's, all the 'b's, and so on.
Do the exact same thing for the second bag of letter tiles.
Now, compare the counts for each letter type between the two bags.
For each letter, if the first bag has more of that letter than the second bag, those extra letters from the first bag would need to be changed.
Similarly, if the second bag has more of a letter than the first bag, those extra letters from the second bag would also need to be changed.
Sum up all the 'extra' letters from both bags. This total represents the minimum number of letters you'd need to change in one string to match the other, making them anagrams.

Code Implementation

def min_steps_to_make_anagrams(string_one, string_two):
    character_counts_one = {}
    character_counts_two = {}

    # Count characters in the first string.
    for character in string_one:
        character_counts_one[character] = character_counts_one.get(character, 0) + 1

    # Count characters in the second string.
    for character in string_two:
        character_counts_two[character] = character_counts_two.get(character, 0) + 1

    total_steps_required = 0

    # Iterate through all possible lowercase English alphabet characters.
    for ascii_value in range(ord('a'), ord('z') + 1):
        current_character = chr(ascii_value)
        count_in_one = character_counts_one.get(current_character, 0)
        count_in_two = character_counts_two.get(current_character, 0)

        # If counts differ, we need to change the excess characters.
        if count_in_one > count_in_two:
            total_steps_required += count_in_one - count_in_two
        elif count_in_two > count_in_one:
            total_steps_required += count_in_two - count_in_one

    return total_steps_required

Big(O) Analysis

Time Complexity

O(n) – Let n be the length of the input strings. We iterate through each string once to build frequency maps (or arrays) for characters. This takes O(n) time for each string, resulting in O(n) + O(n) = O(n) time. Then, we iterate through the alphabet (a fixed size, typically 26 characters) to compare the counts. This comparison step takes constant time, O(1), as the alphabet size is constant regardless of the input string length. Therefore, the dominant factor is the initial iteration through the strings, leading to a total time complexity of O(n).

Space Complexity

O(1) – The solution uses a fixed-size array (typically of size 26 for lowercase English alphabets) to store character counts. This array's size does not depend on the length of the input strings, N. Therefore, the auxiliary space complexity remains constant regardless of the input size.

Edge Cases

Case	How to Handle
Both input strings are empty	If both strings are empty, they are anagrams of each other, requiring zero steps.
One input string is empty, the other is not	The number of steps required is the length of the non-empty string, as all its characters must be replaced.
Input strings have different lengths	The problem implies strings of potentially different lengths, and the solution should calculate differences in character counts to determine replacements.
Input strings contain only lowercase English letters	A frequency map or array of size 26 is sufficient to track character counts efficiently.
Input strings contain characters outside the English alphabet (e.g., numbers, symbols, uppercase)	The solution should ideally be extended to handle a wider character set or clearly define its limitations.
One string is an anagram of the other with no changes needed	The algorithm will correctly compute zero steps as all character counts will match.
One string requires all characters to be replaced to become an anagram of the other	The difference in character counts will accurately reflect the maximum number of replacements needed.
Strings with very large lengths	The frequency map approach scales linearly with string length, making it efficient for large inputs.

Both input strings are empty

How to Handle:

If both strings are empty, they are anagrams of each other, requiring zero steps.

One input string is empty, the other is not

How to Handle:

The number of steps required is the length of the non-empty string, as all its characters must be replaced.

Input strings have different lengths

How to Handle:

The problem implies strings of potentially different lengths, and the solution should calculate differences in character counts to determine replacements.

Input strings contain only lowercase English letters

How to Handle:

A frequency map or array of size 26 is sufficient to track character counts efficiently.

Input strings contain characters outside the English alphabet (e.g., numbers, symbols, uppercase)

How to Handle:

The solution should ideally be extended to handle a wider character set or clearly define its limitations.

One string is an anagram of the other with no changes needed

How to Handle:

The algorithm will correctly compute zero steps as all character counts will match.

One string requires all characters to be replaced to become an anagram of the other

How to Handle:

The difference in character counts will accurately reflect the maximum number of replacements needed.

Strings with very large lengths

How to Handle:

The frequency map approach scales linearly with string length, making it efficient for large inputs.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the input strings `s` and `t` guaranteed to be non-empty?
Are the input strings composed only of lowercase English letters, or can they contain uppercase letters, numbers, or special characters?
If `s` and `t` have different lengths, what is the expected behavior?
Can the input strings contain Unicode characters, or should I assume ASCII only?
Are there any implicit constraints on the maximum length of the strings `s` and `t`?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Think about each character in the first string.
For each character in the first string, consider if it exists in the second string.
If a character from the first string is found in the second string, we can think of that as a match, and we don't need to change it.
If a character from the first string is NOT found in the second string, we'll need to change it (either by adding it to the second string or removing it from the first).
Now, do the same for each character in the second string, checking if it exists in the first string.
If a character from the second string is NOT found in the first string, it also needs to be changed.
Count up all the characters that didn't have a match in the other string.
The total count of these unmatched characters represents the minimum number of changes needed.

Code Implementation

def minSteps(string_one, string_two):
    unmatched_characters_count = 0
    
    # We need a mutable copy of string_two to remove characters as we find matches
    mutable_string_two = list(string_two)
    
    # Iterate through each character in the first string to find matches in the second
    for character_one in string_one:
        found_match_in_string_two = False
        for index_two in range(len(mutable_string_two)):
            if character_one == mutable_string_two[index_two]:
                # Once a match is found, remove it from the second string's mutable copy
                mutable_string_two.pop(index_two)
                found_match_in_string_two = True
                break
        if not found_match_in_string_two:
            # If a character from string_one is not found in string_two, it needs changing
            unmatched_characters_count += 1
            
    # Any remaining characters in mutable_string_two are also unmatched and need changing
    unmatched_characters_count += len(mutable_string_two)
    
    return unmatched_characters_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have two bags of letter tiles, one for each string.
Go through the first bag and count how many of each type of letter you have. For example, count all the 'a's, all the 'b's, and so on.
Do the exact same thing for the second bag of letter tiles.
Now, compare the counts for each letter type between the two bags.
For each letter, if the first bag has more of that letter than the second bag, those extra letters from the first bag would need to be changed.
Similarly, if the second bag has more of a letter than the first bag, those extra letters from the second bag would also need to be changed.
Sum up all the 'extra' letters from both bags. This total represents the minimum number of letters you'd need to change in one string to match the other, making them anagrams.

Code Implementation

def min_steps_to_make_anagrams(string_one, string_two):
    character_counts_one = {}
    character_counts_two = {}

    # Count characters in the first string.
    for character in string_one:
        character_counts_one[character] = character_counts_one.get(character, 0) + 1

    # Count characters in the second string.
    for character in string_two:
        character_counts_two[character] = character_counts_two.get(character, 0) + 1

    total_steps_required = 0

    # Iterate through all possible lowercase English alphabet characters.
    for ascii_value in range(ord('a'), ord('z') + 1):
        current_character = chr(ascii_value)
        count_in_one = character_counts_one.get(current_character, 0)
        count_in_two = character_counts_two.get(current_character, 0)

        # If counts differ, we need to change the excess characters.
        if count_in_one > count_in_two:
            total_steps_required += count_in_one - count_in_two
        elif count_in_two > count_in_one:
            total_steps_required += count_in_two - count_in_one

    return total_steps_required

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both input strings are empty	If both strings are empty, they are anagrams of each other, requiring zero steps.
One input string is empty, the other is not	The number of steps required is the length of the non-empty string, as all its characters must be replaced.
Input strings have different lengths	The problem implies strings of potentially different lengths, and the solution should calculate differences in character counts to determine replacements.
Input strings contain only lowercase English letters	A frequency map or array of size 26 is sufficient to track character counts efficiently.
Input strings contain characters outside the English alphabet (e.g., numbers, symbols, uppercase)	The solution should ideally be extended to handle a wider character set or clearly define its limitations.
One string is an anagram of the other with no changes needed	The algorithm will correctly compute zero steps as all character counts will match.
One string requires all characters to be replaced to become an anagram of the other	The difference in character counts will accurately reflect the maximum number of replacements needed.
Strings with very large lengths	The frequency map approach scales linearly with string length, making it efficient for large inputs.

Both input strings are empty

How to Handle:

If both strings are empty, they are anagrams of each other, requiring zero steps.

One input string is empty, the other is not

How to Handle:

The number of steps required is the length of the non-empty string, as all its characters must be replaced.

Input strings have different lengths

How to Handle:

The problem implies strings of potentially different lengths, and the solution should calculate differences in character counts to determine replacements.

Input strings contain only lowercase English letters

How to Handle:

A frequency map or array of size 26 is sufficient to track character counts efficiently.

Input strings contain characters outside the English alphabet (e.g., numbers, symbols, uppercase)

How to Handle:

The solution should ideally be extended to handle a wider character set or clearly define its limitations.

One string is an anagram of the other with no changes needed

How to Handle:

The algorithm will correctly compute zero steps as all character counts will match.

One string requires all characters to be replaced to become an anagram of the other

How to Handle:

The difference in character counts will accurately reflect the maximum number of replacements needed.

Strings with very large lengths

How to Handle:

The frequency map approach scales linearly with string length, making it efficient for large inputs.