# Minimum Deletions to Make String Balanced
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-deletions-to-make-string-balanced)
Canonical: https://scaleengineer.com/dsa/problems/minimum-deletions-to-make-string-balanced
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String, Stack
**Companies:** [redbus](https://scaleengineer.com/companies/redbus)
---
## Problem
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 <= 105`
* `s[i]` is `'a'` or `'b'`​​.

# Approaches
## Brute Force by Iterating All Split Points
This approach is based on the observation that any balanced string must be of the form `aaa...abbb...b`. This implies there is a conceptual "split point" in the string, before which all characters should be 'a' and after which all characters should be 'b'.

We can test every possible split point. A split point at index `i` means we want the final string to be `s[0...i-1]` (as all 'a's) followed by `s[i...n-1]` (as all 'b's). To achieve this, we must delete all 'b's from the prefix and all 'a's from the suffix. By calculating this cost for every possible split point from `0` to `n` and taking the minimum, we can find the answer.
**Time:** O(n^2), where n is the length of the string. The outer loop runs `n+1` times, and for each iteration, the inner loops scan the string, taking O(n) time in total. · **Space:** O(1), as we only use a few variables to store the counts and the minimum value, regardless of the input size.
**Pros:** It is a straightforward and easy-to-understand implementation of the core idea.; It uses constant extra space.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The algorithm iterates through all `n+1` possible positions for the split point. For each position `i`, it performs two nested loops: one to count the 'b's that need to be deleted from the prefix `s[0...i-1]`, and another to count the 'a's that need to be deleted from the suffix `s[i...n-1]`. The sum of these counts gives the total deletions for that specific split configuration. The overall minimum across all configurations is maintained and returned as the result.

```java
class Solution {
    public int minimumDeletions(String s) {
        int n = s.length();
        int minDeletions = n;

        // Iterate through all possible split points
        // i represents the start of the 'b' section
        for (int i = 0; i <= n; i++) {
            int currentDeletions = 0;
            // Count 'b's to delete in the prefix s[0...i-1]
            for (int j = 0; j < i; j++) {
                if (s.charAt(j) == 'b') {
                    currentDeletions++;
                }
            }
            // Count 'a's to delete in the suffix s[i...n-1]
            for (int j = i; j < n; j++) {
                if (s.charAt(j) == 'a') {
                    currentDeletions++;
                }
            }
            minDeletions = Math.min(minDeletions, currentDeletions);
        }
        return minDeletions;
    }
}
```
### Algorithm
- Initialize `minDeletions` to `n`, the length of the string.
- Iterate through every possible split point `i` from `0` to `n`.
- For each split point `i`, we consider the prefix `s[0...i-1]` to be the 'a' section and the suffix `s[i...n-1]` to be the 'b' section.
- Inside the loop, calculate the number of deletions required for this split:
  - Count the number of 'b's in the prefix `s[0...i-1]`. These must be deleted.
  - Count the number of 'a's in the suffix `s[i...n-1]`. These must be deleted.
- Sum these two counts to get the total deletions for the current split point.
- Update `minDeletions` with the minimum value found so far.
- After checking all split points, return `minDeletions`.

## Optimized Approach with Prefix and Suffix Counts
The brute-force approach is slow because it repeatedly recalculates the number of 'a's and 'b's in prefixes and suffixes. We can significantly optimize this by pre-calculating these counts.

This approach uses two auxiliary arrays. The first array, `prefixB`, stores the number of 'b's encountered up to each index. The second array, `suffixA`, stores the number of 'a's from each index to the end of the string. Once these arrays are populated, we can find the deletion cost for any split point `i` in O(1) time by simply summing `prefixB[i]` and `suffixA[i]`. This reduces the overall time complexity to be linear.
**Time:** O(n), as it involves three separate passes over the string (or arrays of its size), each taking linear time. · **Space:** O(n), for the two arrays `prefixB` and `suffixA`, each of size `n+1`.
**Pros:** Efficient O(n) time complexity, which passes the given constraints.; The logic is a clear optimization of the brute-force approach.
**Cons:** Requires O(n) extra space for the prefix and suffix arrays, which might be a concern for very large inputs under strict memory constraints.
### Explanation
First, we iterate through the string from left to right to build the `prefixB` array. `prefixB[i+1]` is calculated based on `prefixB[i]` and the character `s.charAt(i)`. Next, we iterate from right to left to build the `suffixA` array similarly. With these two arrays, we can find the cost for any split point `i` instantly. We loop one final time from `i = 0` to `n`, calculate `prefixB[i] + suffixA[i]`, and find the minimum among them.

```java
class Solution {
    public int minimumDeletions(String s) {
        int n = s.length();
        int[] prefixB = new int[n + 1];
        int[] suffixA = new int[n + 1];

        // Calculate prefix sums of 'b's
        // prefixB[i] = count of 'b's in s[0...i-1]
        for (int i = 0; i < n; i++) {
            prefixB[i + 1] = prefixB[i] + (s.charAt(i) == 'b' ? 1 : 0);
        }

        // Calculate suffix sums of 'a's
        // suffixA[i] = count of 'a's in s[i...n-1]
        for (int i = n - 1; i >= 0; i--) {
            suffixA[i] = suffixA[i + 1] + (s.charAt(i) == 'a' ? 1 : 0);
        }

        int minDeletions = n;
        // Find the minimum deletions for each possible split point
        for (int i = 0; i <= n; i++) {
            minDeletions = Math.min(minDeletions, prefixB[i] + suffixA[i]);
        }

        return minDeletions;
    }
}
```
### Algorithm
- Get the length of the string, `n`.
- Create an array `prefixB` of size `n+1`. `prefixB[i]` will store the count of 'b's in `s[0...i-1]`.
- Populate `prefixB` in a single pass from left to right.
- Create an array `suffixA` of size `n+1`. `suffixA[i]` will store the count of 'a's in `s[i...n-1]`.
- Populate `suffixA` in a single pass from right to left.
- Initialize `minDeletions` to `n`.
- Iterate `i` from `0` to `n`. For each `i`, the number of deletions for a split at `i` is `prefixB[i] + suffixA[i]`.
- Update `minDeletions = min(minDeletions, prefixB[i] + suffixA[i])`.
- Return `minDeletions`.

## Single Pass with Constant Space (Dynamic Programming)
This is the most optimal approach, achieving linear time complexity with constant extra space. It can be viewed as a dynamic programming approach. We iterate through the string once, maintaining a count of the 'b's seen so far (`bCount`) and the minimum deletions needed to balance the prefix processed so far (`minDeletions`).

When we encounter an 'a', it potentially conflicts with previous 'b's. We make a local, optimal decision: either delete this 'a' (adding 1 to our running `minDeletions` count) or keep this 'a' by deleting all previously seen 'b's (costing `bCount` deletions). By always choosing the minimum of these two options, we ensure that `minDeletions` correctly tracks the minimum deletions needed for the prefix ending at the current character. The final value after the loop is the answer for the entire string.
**Time:** O(n), as it requires only a single pass through the string. · **Space:** O(1), as it only uses a fixed number of variables (`minDeletions`, `bCount`).
**Pros:** Extremely efficient, with the best possible time and space complexity.; Solves the problem in a single pass through the string.
**Cons:** The logic can be slightly less intuitive to derive compared to the split-point based approaches.
### Explanation
We use two variables: `bCount` to count the number of 'b's encountered, and `minDeletions` to store the minimum deletions needed. We traverse the string. If the character is 'b', we increment `bCount`. If it's 'a', we face a choice. The cost to make the current prefix balanced is the minimum of either deleting this 'a' (cost `minDeletions + 1`) or deleting all prior 'b's (cost `bCount`). The state `minDeletions` is updated at each 'a' to reflect this optimal choice. This way, we build up the solution one character at a time without needing extra storage.

```java
class Solution {
    public int minimumDeletions(String s) {
        int minDeletions = 0;
        int bCount = 0;

        // minDeletions acts as the result of a DP state: 
        // min deletions to balance the prefix s[0...i]
        for (char c : s.toCharArray()) {
            if (c == 'b') {
                bCount++;
            } else { // c == 'a'
                // Two options to balance the prefix ending at this 'a':
                // 1. Delete this 'a'. Deletions increase by 1.
                //    The cost would be the deletions for the previous prefix + 1.
                //    Cost = minDeletions + 1
                // 2. Keep this 'a'. To do so, we must delete all previous 'b's.
                //    Cost = bCount
                // We take the minimum of these two options.
                minDeletions = Math.min(minDeletions + 1, bCount);
            }
        }
        return minDeletions;
    }
}
```
### Algorithm
- Initialize `minDeletions = 0` and `bCount = 0`.
- Iterate through each character `c` of the string `s` from left to right.
- If `c` is 'b', it doesn't violate the balanced condition with the prefix seen so far. We just increment `bCount`.
- If `c` is 'a', it may create a `b...a` imbalance with the `bCount` 'b's we have already seen.
- To fix this, we have two choices:
  1. Delete the current 'a'. The cost is 1 plus the deletions we already decided on for the prefix. The new total is `minDeletions + 1`.
  2. Keep the current 'a'. This forces us to delete all `bCount` 'b's seen before it. The cost for this choice is `bCount`.
- We should choose the more optimal of these two choices. So, we update `minDeletions = min(minDeletions + 1, bCount)`.
- After iterating through the entire string, `minDeletions` will hold the minimum number of deletions required.

# Solutions
### Java

```java
class Solution { public int minimumDeletions ( String s ) { int n = s . length (); int [] f = new int [ n + 1 ]; int b = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { if ( s . charAt ( i - 1 ) == 'b' ) { f [ i ] = f [ i - 1 ]; ++ b ; } else { f [ i ] = Math . min ( f [ i - 1 ] + 1 , b ); } } return f [ n ]; } }
```

### JavaScript

```javascript
/** * @param {string} s * @return {number} */ var minimumDeletions = function (
  s,
) {
  const n = s.length;
  const f = new Array(n + 1).fill(0);
  let b = 0;
  for (let i = 1; i <= n; ++i) {
    if (s[i - 1] === " b ") {
      f[i] = f[i - 1];
      ++b;
    } else {
      f[i] = Math.min(f[i - 1] + 1, b);
    }
  }
  return f[n];
};

```

### Python

```python
class Solution : def minimumDeletions ( self , s : str ) -> int : n = len ( s ) f = [ 0 ] * ( n + 1 ) b = 0 for i , c in enumerate ( s , 1 ): if c == 'b' : f [ i ] = f [ i - 1 ] b += 1 else : f [ i ] = min ( f [ i - 1 ] + 1 , b ) return f [ n ]
```

### CPP

```cpp
class Solution { public: int minimumDeletions ( string s ) { int n = s . size (); int f [ n + 1 ]; memset ( f , 0 , sizeof ( f )); int b = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { if ( s [ i - 1 ] == 'b' ) { f [ i ] = f [ i - 1 ]; ++ b ; } else { f [ i ] = min ( f [ i - 1 ] + 1 , b ); } } return f [ n ]; } };
```