Scale Engineer

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
StringStack
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 <= 105
  • 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.

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;    }}

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.

Solutions

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

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 →

Next problem