Jobs

Interviews

Discussions

Minimum Deletions to Make String Balanced

Medium

Google

5 views

Topics:

StringsDynamic Programming

You are given a string s consisting only of characters 'a' and 'b'.

You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make s balanced.

Example 1:

Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").

Example 2:

Input: s = "bbaaaaabb"
Output: 2
Explanation: The only solution is to delete the first two characters.

Constraints:

1 <= s.length <= 10⁵
s[i] is 'a' or 'b'.

Try coding it in LeetCode

Minimum Deletions to Make String Balanced

Medium

Google

5 views

Topics:

StringsDynamic Programming

You are given a string s consisting only of characters 'a' and 'b'.

You can delete any number of characters in s to make s balanced. s is balanced if there is no pair of indices (i,j) such that i < j and s[i] = 'b' and s[j]= 'a'.

Return the minimum number of deletions needed to make s balanced.

Example 1:

Input: s = "aababbab"
Output: 2
Explanation: You can either:
Delete the characters at 0-indexed positions 2 and 6 ("aababbab" -> "aaabbb"), or
Delete the characters at 0-indexed positions 3 and 6 ("aababbab" -> "aabbbb").

Example 2:

Input: s = "bbaaaaabb"
Output: 2
Explanation: The only solution is to delete the first two characters.

Constraints:

1 <= s.length <= 10⁵
s[i] is 'a' or 'b'.

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:

What characters can appear in the string? Is it strictly limited to 'a' and 'b'?
Is the input string guaranteed to be non-null and non-empty?
If the string is already balanced (e.g., empty or all 'a's or all 'b's), should I return 0?
By 'balanced,' do you mean the string can be divided into two parts, where the left part contains only 'a' and the right part contains only 'b'?
Are there any specific constraints on the length of the input string beyond what an integer can represent?

Brute Force Solution

Approach

The brute force way to solve this is to try removing every possible combination of letters from the string. For each combination, we check if the resulting string is balanced and keep track of the smallest number of removals it took to achieve that.

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

First, consider removing no letters at all. Check if the original string is balanced.
Next, try removing one letter at a time, and for each of these new strings, check if it's balanced.
Then, try removing two letters at a time, considering every possible pair of letters to remove. Check if each resulting string is balanced.
Continue this process, removing three letters, then four, and so on, until you've considered removing all possible combinations of letters up to the point of removing all letters from the original string.
For each string you create by removing letters, determine if it is balanced (meaning all 'a's come before all 'b's).
Keep track of the smallest number of letters you had to remove to get a balanced string.
The smallest number of removals you found is your answer.

Code Implementation

def minimum_deletions_to_make_string_balanced_brute_force(input_string):
    minimum_deletions = len(input_string)

    for i in range(1 << len(input_string)):
        current_string = ""
        deletions_count = 0

        for j in range(len(input_string)):
            if (i >> j) & 1:
                current_string += input_string[j]
            else:
                deletions_count += 1

        # Check if the current string is balanced
        is_balanced = True
        b_found = False
        for char in current_string:
            if char == 'b':
                b_found = True
            if char == 'a' and b_found:
                is_balanced = False
                break

        #If balanced, check if the number of deletions is minimal
        if is_balanced:
            minimum_deletions = min(minimum_deletions, deletions_count)

    return minimum_deletions

Big(O) Analysis

Time Complexity

O(2^n * n) – The algorithm considers all possible subsets of the input string of length n. There are 2^n such subsets. For each subset, it checks if the resulting string is balanced. Checking for balance requires iterating through the string which takes O(n) time in the worst case. Thus, the overall time complexity is O(2^n * n).

Space Complexity

O(N*2^N) – The brute force solution, as described, explores all possible subsets of characters to remove. For each subset (of which there are 2^N), a copy of the string (at most of length N) needs to be created and checked for balance. Therefore, the space required to store these intermediate strings in the worst case is proportional to N*2^N, dominating any other constant space usage. Hence the space complexity is O(N*2^N).

Optimal Solution

Approach

The goal is to find the fewest changes needed to make a string follow the pattern: all 'a's come before all 'b's. We can efficiently determine this by keeping track of the 'a's and 'b's we see as we go through the string, figuring out the best place to split the string into 'a's and 'b's.

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

Start by imagining a line dividing the string into a left part that should only have 'a's and a right part that should only have 'b's.
Move this line from the very beginning to the very end of the string, one position at a time.
At each position of the line, count how many 'b's are on the left side (which should be 'a's) and how many 'a's are on the right side (which should be 'b's). These are the changes needed if we put the line there.
Keep track of the smallest number of changes we've seen so far.
After checking every possible position of the line, the smallest number of changes we found is the answer: the minimum number of deletions to make the string balanced.

Code Implementation

def minDeletions(input_string): 
    left_b_count = 0
    right_a_count = input_string.count('a')
    minimum_deletions = right_a_count

    #Iterate to find optimal split
    for index in range(len(input_string)): 
        if input_string[index] == 'b':
            left_b_count += 1
        else:
            right_a_count -= 1

        # Update min deletions needed to balance string
        minimum_deletions = min(minimum_deletions, left_b_count + right_a_count)

    return minimum_deletions

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string once, moving an imaginary line to determine the minimum number of operations required to make the string balanced. Inside the loop, it counts the number of 'b's on the left and the number of 'a's on the right of the imaginary line. These counts are updated incrementally during each iteration and take constant time. Therefore, the dominant operation is the single pass through the string, resulting in a time complexity of O(n), where n is the length of the string.

Space Complexity

O(1) – The algorithm only uses a few integer variables to keep track of the minimum number of changes and the counts of 'a's and 'b's encountered so far. The space required for these variables remains constant regardless of the input string's length (N). Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty string input	Return 0, as an empty string is already balanced by definition.
String of length 1 or 2	Check if the string is already balanced; if not, a single deletion is needed.
String with all 'a' characters	Return 0, as the string is already balanced.
String with all 'b' characters	Return 0, as the string is already balanced.
String with a long sequence of 'b' followed by a long sequence of 'a'	This will likely result in the maximum number of deletions.
String with alternating 'a' and 'b' characters	A dynamic programming approach calculates the minimum deletions effectively
Maximum string length (considering memory constraints)	The DP array's size should be carefully considered to avoid exceeding memory limits, possibly requiring optimization techniques.
Very long string with skewed distribution favoring a's at the beginning and b's at the end	The solution should efficiently handle large input sizes without significant performance degradation.

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:

What characters can appear in the string? Is it strictly limited to 'a' and 'b'?
Is the input string guaranteed to be non-null and non-empty?
If the string is already balanced (e.g., empty or all 'a's or all 'b's), should I return 0?
By 'balanced,' do you mean the string can be divided into two parts, where the left part contains only 'a' and the right part contains only 'b'?
Are there any specific constraints on the length of the input string beyond what an integer can represent?

Brute Force Solution

Approach

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

First, consider removing no letters at all. Check if the original string is balanced.
Next, try removing one letter at a time, and for each of these new strings, check if it's balanced.
Then, try removing two letters at a time, considering every possible pair of letters to remove. Check if each resulting string is balanced.
Continue this process, removing three letters, then four, and so on, until you've considered removing all possible combinations of letters up to the point of removing all letters from the original string.
For each string you create by removing letters, determine if it is balanced (meaning all 'a's come before all 'b's).
Keep track of the smallest number of letters you had to remove to get a balanced string.
The smallest number of removals you found is your answer.

Code Implementation

def minimum_deletions_to_make_string_balanced_brute_force(input_string):
    minimum_deletions = len(input_string)

    for i in range(1 << len(input_string)):
        current_string = ""
        deletions_count = 0

        for j in range(len(input_string)):
            if (i >> j) & 1:
                current_string += input_string[j]
            else:
                deletions_count += 1

        # Check if the current string is balanced
        is_balanced = True
        b_found = False
        for char in current_string:
            if char == 'b':
                b_found = True
            if char == 'a' and b_found:
                is_balanced = False
                break

        #If balanced, check if the number of deletions is minimal
        if is_balanced:
            minimum_deletions = min(minimum_deletions, deletions_count)

    return minimum_deletions

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by imagining a line dividing the string into a left part that should only have 'a's and a right part that should only have 'b's.
Move this line from the very beginning to the very end of the string, one position at a time.
At each position of the line, count how many 'b's are on the left side (which should be 'a's) and how many 'a's are on the right side (which should be 'b's). These are the changes needed if we put the line there.
Keep track of the smallest number of changes we've seen so far.
After checking every possible position of the line, the smallest number of changes we found is the answer: the minimum number of deletions to make the string balanced.

Code Implementation

def minDeletions(input_string): 
    left_b_count = 0
    right_a_count = input_string.count('a')
    minimum_deletions = right_a_count

    #Iterate to find optimal split
    for index in range(len(input_string)): 
        if input_string[index] == 'b':
            left_b_count += 1
        else:
            right_a_count -= 1

        # Update min deletions needed to balance string
        minimum_deletions = min(minimum_deletions, left_b_count + right_a_count)

    return minimum_deletions

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return 0, as an empty string is already balanced by definition.
String of length 1 or 2	Check if the string is already balanced; if not, a single deletion is needed.
String with all 'a' characters	Return 0, as the string is already balanced.
String with all 'b' characters	Return 0, as the string is already balanced.
String with a long sequence of 'b' followed by a long sequence of 'a'	This will likely result in the maximum number of deletions.
String with alternating 'a' and 'b' characters	A dynamic programming approach calculates the minimum deletions effectively
Maximum string length (considering memory constraints)	The DP array's size should be carefully considered to avoid exceeding memory limits, possibly requiring optimization techniques.
Very long string with skewed distribution favoring a's at the beginning and b's at the end	The solution should efficiently handle large input sizes without significant performance degradation.