Show problems as
Classic problem #921MediumStringStackGreedyBracket Sequences

Minimum Add to Make Parentheses Valid

Real-world version: Repairing the Bracket Log
Tracked in this browser only
Read Minimum Add to Make Parentheses Valid on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A scanner read a page of handwritten algebra and kept only the round brackets, throwing away every other mark. What survives is the string s, holding the brackets in the order they were written; each character of s is either '(' or ')'.

Call a bracket log settled when it reads as a correct nesting. Precisely, a log is settled if it is empty, or if it is one settled log written straight after another, or if it is a settled log with a '(' put in front of it and a ')' put after it.

An editor may type single brackets back into the log at any positions, including the very start and the very end, but may never delete or move a bracket that is already there. Return the fewest brackets the editor has to type so that the log becomes settled.

Examples

Example 1

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

The first two characters already pair with each other. The two closes that follow have nothing standing before them to pair with, and the two opens at the end have nothing after them, so an open is typed before each of those closes and a close after each of those opens.

Example 2

Input
s = ")("
Output
2

The log as scanned has a close before an open. Typing one open at the very start and one close at the very end settles it.

Example 3

Input
s = "()"
Output
0

The log already reads as a correct nesting, so the editor types nothing.

Example 4

Input
s = ")))((("
Output
6

Each of the three leading closes needs an open typed before it, and each of the three trailing opens needs a close typed after it.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_add_to_make_valid(s: str) -> int:
Java
public int minAddToMakeValid(String s)

More on the same topics