Minimum Insertions to Balance a Parentheses String

medium string stack greedy

Problem

A string is balanced if every '(' must be followed by '))'. Given a string of '(' and ')', return the minimum number of insertions needed to make it balanced.

Inputs = "(()))"

Output1

Insert one ')' to obtain "(())))" — every '(' is followed by '))'.

s (parentheses)

def min_insertions(s):
    ans = need = 0
    i, n = 0, len(s)
    while i < n:
        if s[i] == '(':
            need += 2
            if need % 2:        # odd → insert one ')'
                ans += 1; need -= 1
            i += 1
        else:
            if need == 0:       # extra ')': insert '('
                ans += 1; need = 1
            need -= 1
            i += 1
    return ans + need

function minInsertions(s) {
  let ans = 0, need = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      need += 2;
      if (need % 2) { ans++; need--; }
    } else {
      if (need === 0) { ans++; need = 1; }
      need--;
    }
  }
  return ans + need;
}

class Solution {
    public int minInsertions(String s) {
        int ans = 0, need = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                need += 2;
                if (need % 2 != 0) { ans++; need--; }
            } else {
                if (need == 0) { ans++; need = 1; }
                need--;
            }
        }
        return ans + need;
    }
}

int minInsertions(string s) {
    int ans = 0, need = 0;
    for (char c : s) {
        if (c == '(') {
            need += 2;
            if (need % 2) { ans++; need--; }
        } else {
            if (need == 0) { ans++; need = 1; }
            need--;
        }
    }
    return ans + need;
}

Explanation

The twist in this problem is that every ( must be closed by two ), not one. We do a single pass keeping ans (insertions made so far) and need (how many ) are still owed).

When we see (, it demands two closers, so need += 2. But need must stay even, because closers come in pairs. If need turns odd, the previous group was short one ), so we insert one (ans++) and drop need back to even.

When we see ), if nothing is owed (need == 0) this closer is orphaned and needs a ( in front of it, so ans++ and set need = 1 to pretend an opener exists. Either way we then consume one closer with need--.

Example: s = "(()))". The two ( raise need to 4 (paired up nicely). Then three ) bring need down to 1. At the end we still owe need = 1 closer, so the total is ans + need = 0 + 1 = 1.

It works because need always reflects the exact unmet closing demand, and forcing it to stay even captures the rule that each opener needs a pair of closers.

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