Minimum Deletions to Make String Balanced

Minimum Deletions to Make String Balanced - 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. A string 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.

Input & Output

Example 1 — Mixed String

$ Input: s = "aababbab"

› Output: 2

💡 Note: Remove the two 'b's at positions 2 and 4 to get "aaaabb" which is balanced: all 'a's come before all 'b's

Example 2 — Already Balanced

$ Input: s = "bbb"

› Output: 0

💡 Note: String contains only 'b's, so it's already balanced (no 'a' comes after 'b')

Example 3 — Reverse Order

$ Input: s = "baaba"

› Output: 3

💡 Note: One optimal solution is to delete 'b', 'a', and 'b' to get "aa" which is balanced

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either 'a' or 'b'

Visualization

Tap to expand

Understanding the Visualization

Input

String with mixed 'a' and 'b' characters: "aababbab"

Process

Identify positions where 'b' comes before 'a' (imbalance)

Output

Minimum deletions needed: 2

Key Takeaway

🎯 Key Insight: A balanced string must have all 'a's before all 'b's - find the optimal split point to minimize deletions

Asked in

f Facebook 15 a Amazon 12 M Microsoft 8

The key insight is that a balanced string has all 'a's before all 'b's. We can solve this optimally in O(n) time by tracking the running count of 'b's and making deletion decisions when we encounter 'a's. Best approach is single pass with running balance. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass - Running Balance	O(n)	O(1)	Track running balance of A's and B's to find minimum deletions in one pass
Two Pass - Count A's and B's	O(n)	O(n)	Count A's after each position and B's before each position to find optimal split
Brute Force - Try All Subsequences	O(2ⁿ × n)	O(n)	Generate all possible subsequences and check which ones are balanced

Single Pass - Running Balance — Algorithm Steps

Scan string left to right
Track count of B's that need to be balanced
When we see 'a', we can either delete it or delete previous B's
Choose the option that minimizes total deletions

Visualization

Tap to expand

Step-by-Step Walkthrough

Track B's

Count B's as we encounter them

Balance A's

When we see A after B's, decide to delete or balance

Minimize

Make optimal choice at each step

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s) {
    int deletions = 0;
    int bCount = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        if (s[i] == 'b') {
            bCount++;
        } else { // s[i] == 'a'
            // We can either delete this 'a' or delete all previous 'b's
            // Choose the option that requires fewer deletions
            if (bCount > 0) {
                // If there are B's before this A, we need to make a choice
                // Delete this A (cost = 1) or delete one B (cost = 1)
                // We choose to delete one B to maintain balance
                deletions++;
                bCount--;
            }
        }
    }
    
    return deletions;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass - Running Balance — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler