Minimum Deletions to Make String Balanced

Med

#1517Time: 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.1 company

Patterns

Dynamic Programming

Data structures

String Stack

Companies

redbus

Prompt

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'.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int minimumDeletions(String s) {3        int n = s.length();4        int minDeletions = n;5 6        // Iterate through all possible split points7        // i represents the start of the 'b' section8        for (int i = 0; i <= n; i++) {9            int currentDeletions = 0;10            // Count 'b's to delete in the prefix s[0...i-1]11            for (int j = 0; j < i; j++) {12                if (s.charAt(j) == 'b') {13                    currentDeletions++;14                }15            }16            // Count 'a's to delete in the suffix s[i...n-1]17            for (int j = i; j < n; j++) {18                if (s.charAt(j) == 'a') {19                    currentDeletions++;20                }21            }22            minDeletions = Math.min(minDeletions, currentDeletions);23        }24        return minDeletions;25    }26}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int minimumDeletions(String s) {3        int n = s.length();4        int[] prefixB = new int[n + 1];5        int[] suffixA = new int[n + 1];6 7        // Calculate prefix sums of 'b's8        // prefixB[i] = count of 'b's in s[0...i-1]9        for (int i = 0; i < n; i++) {10            prefixB[i + 1] = prefixB[i] + (s.charAt(i) == 'b' ? 1 : 0);11        }12 13        // Calculate suffix sums of 'a's14        // suffixA[i] = count of 'a's in s[i...n-1]15        for (int i = n - 1; i >= 0; i--) {16            suffixA[i] = suffixA[i + 1] + (s.charAt(i) == 'a' ? 1 : 0);17        }18 19        int minDeletions = n;20        // Find the minimum deletions for each possible split point21        for (int i = 0; i <= n; i++) {22            minDeletions = Math.min(minDeletions, prefixB[i] + suffixA[i]);23        }24 25        return minDeletions;26    }27}

Complexity

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`.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int minimumDeletions(String s) {3        int minDeletions = 0;4        int bCount = 0;5 6        // minDeletions acts as the result of a DP state: 7        // min deletions to balance the prefix s[0...i]8        for (char c : s.toCharArray()) {9            if (c == 'b') {10                bCount++;11            } else { // c == 'a'12                // Two options to balance the prefix ending at this 'a':13                // 1. Delete this 'a'. Deletions increase by 1.14                //    The cost would be the deletions for the previous prefix + 1.15                //    Cost = minDeletions + 116                // 2. Keep this 'a'. To do so, we must delete all previous 'b's.17                //    Cost = bCount18                // We take the minimum of these two options.19                minDeletions = Math.min(minDeletions + 1, bCount);20            }21        }22        return minDeletions;23    }24}

Complexity

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`).

Trade-offs

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.

Solutions

Solution

1class 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 ]; } }

1/** * @param {string} s * @return {number} */ var minimumDeletions = function (2  s,3) {4  const n = s.length;5  const f = new Array(n + 1).fill(0);6  let b = 0;7  for (let i = 1; i <= n; ++i) {8    if (s[i - 1] === " b ") {9      f[i] = f[i - 1];10      ++b;11    } else {12      f[i] = Math.min(f[i - 1] + 1, b);13    }14  }15  return f[n];16};

1class 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 ]

1class 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 ]; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class 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 ]; } }

1/** * @param {string} s * @return {number} */ var minimumDeletions = function (2  s,3) {4  const n = s.length;5  const f = new Array(n + 1).fill(0);6  let b = 0;7  for (let i = 1; i <= n; ++i) {8    if (s[i - 1] === " b ") {9      f[i] = f[i - 1];10      ++b;11    } else {12      f[i] = Math.min(f[i - 1] + 1, b);13    }14  }15  return f[n];16};

1class 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 ]

1class 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 ]; } };

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.