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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Minimum Add to Make Parentheses Valid and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →