Skip to main content

921. Minimum Add to Make Parentheses Valid

medium

Count the fewest insertions of '(' or ')' to make a string of parentheses balanced. Lives in the 'Valid Parentheses' family but solves with two counters — the stack collapses to two integers.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

A parentheses string is valid if and only if: it is the empty string, or it can be written as AB (A concatenated with B), where A and B are valid strings, or it can be written as (A), where A is a valid string. You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. Return the minimum number of moves required to make s valid.

Constraints

  • 1 <= s.length <= 1000
  • s[i] is either '(' or ')'.

Examples

Example 1

Input
s = "())"
Output
1

Example 2

Input
s = "((("
Output
3

Example 3

Input
s = "()"
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two kinds of broken parens: ')' with no matching opener, and '(' with no matching closer. Count both.

Hint 2

Walk left to right. On '(', increment 'open'. On ')', either match it (decrement open) or count it as unmatched.

Hint 3

Answer = unmatched closers + leftover open at the end.

Hint 4

This is the same idea as a matching-bracket stack — but you only need its size, not its contents.

Solution approach

Reveal approach

Two-counter pass. Track open (unmatched '(' so far) and ans (unmatched ')' so far). For each c in s: if c == '(', open++. If c == ')', either pair it (open > 0 → open--) or count it as unmatched (ans++). After the loop, ans + open is the number of insertions: each unmatched ')' needs a '(' inserted before it, and each unmatched '(' needs a ')' inserted after it. O(n) time, O(1) space. This is a stack problem where the stack collapses to a single integer because all entries are identical '(' tokens.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • stack
  • string
  • greedy
  • matching-bracket-stack

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Amazon
  • Google

More Stacks practice problems

See all Stacks problems →