Minimum deletions to make string balanced

String Dynamic Programming Stack

68.2% acceptance

Feb 25, 2026

2595

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_deletions(s: String) -> i32 {
    // dp = min deletions to balance prefix so far
    // b_count = number of 'b's in prefix (total)
    let mut dp = 0i32;
    let mut b_count = 0i32;
    for c in s.bytes() {
      if c == b'b' {
        b_count += 1;
      } else {
        // 'a': delete this 'a' (dp+1) or delete all b's before it (b_count)
        dp = (dp + 1).min(b_count);
      }
    }
    dp
  }
}