Minimum Deletions to Make String Balanced

medium dynamic programming string prefix

Problem

You are given a string s of only 'a' and 'b'. The string is balanced when there is no pair of indices i < j with s[i] = 'b' and s[j] = 'a' — i.e. every 'b' comes after every 'a'. Return the minimum number of characters you must delete to make s balanced.

Inputs = "aababbab"

Output2

Delete positions 2 and 6 to get "aaabbb" — two deletions suffice.

Inputs = "bbaaaaabb"

Output2

Delete the two leading b's so all remaining a's precede all b's.

s (only 'a' and 'b')

def min_deletions(s):
    res = 0       # min deletions so far
    b_count = 0   # number of 'b' seen so far
    for ch in s:
        if ch == 'b':
            b_count += 1
        else:
            # delete this 'a', or delete all earlier 'b's
            res = min(res + 1, b_count)
    return res

function minDeletions(s) {
  let res = 0;      // min deletions so far
  let bCount = 0;   // number of 'b' seen so far
  for (const ch of s) {
    if (ch === 'b') {
      bCount++;
    } else {
      // delete this 'a', or delete all earlier 'b's
      res = Math.min(res + 1, bCount);
    }
  }
  return res;
}

int minDeletions(String s) {
    int res = 0;       // min deletions so far
    int bCount = 0;    // number of 'b' seen so far
    for (char ch : s.toCharArray()) {
        if (ch == 'b') {
            bCount++;
        } else {
            // delete this 'a', or delete all earlier 'b's
            res = Math.min(res + 1, bCount);
        }
    }
    return res;
}

int minDeletions(string s) {
    int res = 0;       // min deletions so far
    int bCount = 0;    // number of 'b' seen so far
    for (char ch : s) {
        if (ch == 'b') {
            bCount++;
        } else {
            // delete this 'a', or delete all earlier 'b's
            res = min(res + 1, bCount);
        }
    }
    return res;
}

Explanation

A balanced string looks like aaa...bbb: some block of a's followed by some block of b's. So we scan left to right and ask, at each character, the minimum deletions to keep everything seen so far balanced.

We carry two values. res is the best (minimum) number of deletions to balance the prefix processed so far, and b_count is how many 'b' characters we have seen. Both start at 0.

When the current character is 'b', it can always sit at the tail of a balanced prefix, so it never forces a deletion — we just increment b_count and leave res unchanged.

When the current character is 'a', it conflicts with every earlier 'b'. We have two choices and take the cheaper: delete this 'a' (cost res + 1, keeping all earlier b's), or delete all earlier 'b's (cost b_count, keeping this a). Hence res = min(res + 1, b_count).

This is dynamic programming with the prefix index as the state, compressed to two running scalars. Each character is visited once, so the whole thing is one linear pass with constant extra space.

Time: O(n) Space: O(1)