Minimum insertions to balance a parentheses string

String Stack Greedy

53.5% acceptance

Feb 25, 2026

1261

295

Given a parentheses string s containing only the characters '(' and ')'. A parentheses string is balanced if: Any left parenthesis '(' must have a corresponding two consecutive right parenthesis '))'. Left parenthesis '(' must go before the corresponding two consecutive right parenthesis '))'. You can insert the characters '(' and ')' at any position of the string to balance it if needed. Return the minimum number of insertions needed to make s balanced.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_insertions(s: String) -> i32 {
    let bytes = s.as_bytes();
    let n = bytes.len();
    let mut ans = 0i32;
    let mut open = 0i32; // unmatched '('
    let mut i = 0;
    while i < n {
      if bytes[i] == b'(' {
        open += 1;
        i += 1;
      } else {
        // ')' found
        if i + 1 < n && bytes[i + 1] == b')' {
          // consume "))"
          if open > 0 { open -= 1; } else { ans += 1; } // insert '('
          i += 2;
        } else {
          // single ')' - need to insert another ')'
          ans += 1; // insert ')'
          if open > 0 { open -= 1; } else { ans += 1; } // match or insert '('
          i += 1;
        }
      }
    }
    ans + 2 * open // each unmatched '(' needs "))"
  }
}