LeetCode 1653 - Minimum Deletions to Make String Balanced

LeetCode Problem 1653

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Stack

Solution

Problem Understanding

The problem asks us to make a string containing only characters 'a' and 'b' balanced by deleting the minimum number of characters. A string is considered balanced if there are no occurrences where a 'b' comes before an 'a' in the string. In other words, all 'a' characters must appear before any 'b' characters, or equivalently, the string can be split into a prefix of 'a's followed by a suffix of 'b's, possibly with deletions in between.

The input is a string s of length up to 100,000. The output is a single integer representing the minimum deletions required to achieve the balanced state. The constraints tell us that the solution must be efficient - likely linear time - since quadratic or higher approaches will be too slow.

Important edge cases include strings that are already balanced, strings consisting entirely of 'a's or 'b's, and strings with alternating 'a's and 'b's which may require deletions throughout.

Approaches

The brute-force approach would be to consider every possible subset of deletions to achieve a string of all 'a's followed by all 'b's. This involves checking all combinations, which is computationally infeasible for strings of length up to 100,000 because it has exponential complexity.

The key observation for an optimal solution is that we can process the string linearly while keeping track of two counters: the number of 'b's encountered so far and the minimum number of deletions required. At each position, we have two choices: either delete the current 'a' if it comes after 'b's, or count the current 'b' as part of the sequence that should remain. By iterating through the string and updating the minimum deletions accordingly, we can solve this in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Check all possible deletion subsets to find minimum deletions
Optimal	O(n)	O(1)	Linear scan tracking 'b' count and minimum deletions dynamically

Algorithm Walkthrough

1. Initialize two counters: b_count = 0 to keep track of 'b's encountered and deletions = 0 to store the current minimum deletions needed.
2. Iterate through each character in the string s.
3. If the current character is 'b', increment b_count because it might be part of a valid suffix of 'b's.
4. If the current character is 'a', we have two options: delete this 'a' (increment deletions by 1) or consider deleting some 'b's seen so far to maintain balance. Update deletions to be the minimum of deletions + 1 and b_count.
5. Continue iterating until the end of the string.
6. Return deletions as the minimum number of deletions required to make the string balanced.

Why it works: This algorithm maintains the invariant that at each step, deletions represents the minimum deletions needed for the prefix processed so far to be balanced. It correctly handles the tradeoff between deleting 'a's or 'b's at each conflict point.

Python Solution

class Solution:
    def minimumDeletions(self, s: str) -> int:
        b_count = 0
        deletions = 0
        
        for char in s:
            if char == 'b':
                b_count += 1
            elif char == 'a':
                deletions = min(deletions + 1, b_count)
        
        return deletions

This Python implementation follows the algorithm exactly. We maintain b_count to track the number of 'b's that could be part of the balanced suffix. For each 'a' encountered, we decide whether it is cheaper to delete this 'a' or delete all previous 'b's to maintain balance. The min operation ensures that we always have the minimal deletions at each step.

Go Solution

func minimumDeletions(s string) int {
    bCount := 0
    deletions := 0

    for i := 0; i < len(s); i++ {
        if s[i] == 'b' {
            bCount++
        } else if s[i] == 'a' {
            if deletions+1 < bCount {
                deletions++
            } else {
                deletions = bCount
            }
        }
    }

    return deletions
}

In Go, the logic is identical. We use integer counters for bCount and deletions. The loop iterates over the string using indices. The if statement ensures we choose the minimum between deleting the current 'a' or deleting all preceding 'b's to achieve a balanced prefix.

Worked Examples

Example 1: s = "aababbab"

Step	char	b_count	deletions	Explanation
1	'a'	0	0	No conflict, nothing to delete
2	'a'	0	0	Still balanced
3	'b'	1	0	Increment 'b' count
4	'a'	1	1	Delete this 'a' or remove previous 'b'; min = 1
5	'b'	2	1	Increment 'b' count
6	'b'	3	1	Increment 'b' count
7	'a'	3	2	Delete 'a' or remove all previous 'b'; min = 2
8	'b'	4	2	Increment 'b' count

Output: 2

Example 2: s = "bbaaaaabb"

Step	char	b_count	deletions	Explanation
1	'b'	1	0	Increment 'b' count
2	'b'	2	0	Increment 'b' count
3	'a'	2	1	Delete 'a' or previous 'b'; min = 1
4	'a'	2	2	Delete 'a' or previous 'b'; min = 2
5	'a'	2	2	Deletions remain 2
6	'a'	2	2	Deletions remain 2
7	'a'	2	2	Deletions remain 2
8	'b'	3	2	Increment 'b' count
9	'b'	4	2	Increment 'b' count

Output: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the string once, updating counters in constant time per character
Space	O(1)	Only two integer counters are used, independent of input size

Since the algorithm only needs a single pass through the string and uses constant extra space, it is optimal for the given constraints.

Test Cases

# provided examples
assert Solution().minimumDeletions("aababbab") == 2  # mixed case
assert Solution().minimumDeletions("bbaaaaabb") == 2  # prefix b's, suffix a's

# edge cases
assert Solution().minimumDeletions("aaaa") == 0  # all a's, already balanced
assert Solution().minimumDeletions("bbbb") == 0  # all b's, already balanced
assert Solution().minimumDeletions("abababab") == 4  # alternating characters
assert Solution().minimumDeletions("ba") == 1  # smallest unbalanced case
assert Solution().minimumDeletions("a") == 0  # single character, balanced
assert Solution().minimumDeletions("b") == 0  # single character, balanced
assert Solution().minimumDeletions("baba") == 2  # multiple conflicts

Test	Why
"aababbab"	Mixed characters with deletions required in middle
"bbaaaaabb"	Long prefix of b's requires deletions at start
"aaaa"	Already balanced, no deletions
"bbbb"	Already balanced, no deletions
"abababab"	Alternating pattern, deletes all conflicting characters
"ba"	Smallest unbalanced, tests minimal input
"a"	Single character edge case
"b"	Single character edge case
"baba"	Multiple conflicts to test iterative min logic

Edge Cases

The first edge case is a string composed entirely of 'a's. In this case, no deletions are required because the string is trivially balanced. The algorithm handles this by never incrementing the deletions counter since b_count