Fewest Parentheses to Insert

EasyStack

Problem

A string s contains only ( and ). You may insert parentheses anywhere in it, one character at a time.

Return the minimum number of insertions needed so that the string becomes balanced: every ( is later closed by a ) and no ) appears without an earlier unmatched (.

Example 1

Input:
s = "())"
Output:
1

Insert one ( at the front: "(())".

Example 2

Input:
s = "((("
Output:
3

Example 3

Input:
s = "()))(("
Output:
4

Two ) have no partner and two ( are never closed.

Constraints

  • 0 ≤ s.length ≤ 10^5
  • s contains only '(' and ')'

Hint

Show the first hint

Process the string with the usual matching stack. What is left unmatched at the end?

Walkthrough

How to approach it

01Clarify before coding

  • Can I delete characters? No, only insert.
  • Does it matter where insertions go? No, only the count is returned.

02Brute force

Breadth-first search over strings: try every insertion of ( or ) at every position, level by level, until a balanced string appears.

Cost: Exponential in the number of insertions; hopeless even for short inputs.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.