0416MediumStringStackGreedyBracket Sequences

Repairing the Bracket Log

Tracked in this browser only

Trains the technique from

LeetCode 921Minimum Add to Make Parentheses Valid

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_add_to_make_valid(s: str) -> int:

Java

public int minAddToMakeValid(String s)

The intended approach

Time O(n) for a log of length n: one pass over the characters.Space O(1): two integer counters.

Walk the log once holding a single counter for opening brackets that have not been closed yet. An opening bracket raises it. A closing bracket lowers it when it is above zero, otherwise that closing bracket has nothing before it to pair with and never will, so it is charged one typed bracket immediately. Whatever the counter still holds at the end is the number of opening brackets with no partner, and each of those costs one typed bracket too.

Pythonentry point: min_add_to_make_valid

def min_add_to_make_valid(s):
    # One left-to-right pass. `waiting` holds opens still looking for a close;
    # the moment a close arrives with nothing waiting it can never be matched by
    # anything later, so it is billed at once. O(n) time, O(1) extra space.
    waiting = 0
    inserted = 0
    for mark in s:
        if mark == "(":
            waiting += 1
        elif waiting > 0:
            waiting -= 1
        else:
            inserted += 1
    return inserted + waiting

The obvious version

Strike out any `"()"` that sit side by side, over and over, until no such pair is left. Every bracket still standing has no partner, so the length of the remainder is the count of brackets that must be typed in.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_add_to_make_valid(s):
    text = s
    while "()" in text:
        text = text.replace("()", "")
    return len(text)

How this problem was checked

Reference solution executed against 17 test cases — 17 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in