Minimum Insertions to Balance a Bracket String

Medium15–20 min

Topics

StackStringGreedy

Companies

GoogleAmazonBloomberg

Given a string s consisting only of '(' and ')', find the minimum number of parentheses that need to be inserted anywhere in the string to make it balanced. Unlike checking whether a bracket string is already valid, this asks how far from valid it is. A single running counter does the job in one pass: track how many '(' are currently unmatched. Every ')' either closes one of them (decrement) or, if none are open, is itself unmatched and needs a '(' inserted before it (tally it). Whatever's still open at the very end needs a ')' inserted after it. The total repair cost is exactly the sum of those two kinds of damage — no backtracking or re-scanning required.

Test Case 1:

Input:s = "(()"

Output:1

Explanation:One '(' has no matching ')'. Insert one ')' at the end to balance it.

Test Case 2:

Input:s = "))(("

Output:4

Explanation:Every character here is unmatched — the two ')' at the front have nothing open before them, and the two '(' at the back have nothing closing after them. All 4 need a partner inserted.

Test Case 3:

Input:s = "()()"

Output:0

Explanation:Already perfectly balanced — two separate matched pairs.

Constraints

◆1 ≤ s.length ≤ 10⁴
◆s consists only of the characters '(' and ')'

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Repeatedly Remove Matched Pairs

Brute

Repeatedly scan the string for an adjacent "()" pair and remove it, shrinking the string, until no such pair remains anywhere. Whatever's left is exactly the unmatched characters — every leftover ')' needs a '(' inserted before it, and every leftover '(' needs a ')' inserted after it, so the answer is simply the length of what remains. Each pass over the string is O(n), and up to n/2 passes may be needed, so this costs O(n²) overall.

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public int minInsertionsToBalance(String s) {
        while (s.contains("()")) {
            s = s.replace("()", "");
        }
        return s.length();
    }
}

Optimal — Single Pass With a Running Count

Optimal

Walk the string once, tracking how many unmatched '(' are currently "open" with a simple counter (no actual stack needed, since every open bracket is identical). On '(', increment the counter. On ')', close an open bracket if one is waiting (decrement the counter); if none is waiting, this ')' is unmatched, so tally it as a needed insertion. Whatever's still open at the end also needs a closing insertion. The answer is the unmatched-')' tally plus whatever's left open.

TimeO(n)

SpaceO(1)