Show problems as
Classic problem #1249MediumStringStack

Minimum Remove to Make Valid Parentheses

Real-world version: Trim the Unpaired Brackets
Tracked in this browser only
Read Minimum Remove to Make Valid Parentheses on LeetCode(opens in a new tab)

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

A small macro language writes each step as a string s of lowercase letters and the round brackets ( and ).

Brackets are meant to nest. Reading s from left to right, a ) closes the nearest ( to its left that nothing has closed yet. A step is well formed when every bracket ends up with a partner under that rule.

The linter repairs a step that is not well formed by deleting brackets, and it deletes as few as it can. Which ones go is pinned down: pair the brackets up by the nearest-open rule above, then delete every ) that found no open bracket to close and every ( that never got closed. Letters are never deleted, and every surviving character keeps its original position relative to the others.

Return the string the linter produces.

Examples

Example 1

Input
s = "fo)o(bar)"
Output
"foo(bar)"

The `)` at index 2 has no open bracket waiting to its left, so it is deleted. The `(` at index 4 is closed by the `)` at index 8, so that pair and every letter stay.

Example 2

Input
s = "a(b(c)"
Output
"ab(c)"

The `)` at index 5 closes the nearest unclosed open bracket to its left, which is the `(` at index 3. The `(` at index 1 is then left without a partner, so that is the character deleted.

Example 3

Input
s = "(a)((b"
Output
"(a)b"

The `)` at index 2 closes the `(` at index 0. The open brackets at indices 3 and 4 are never closed, so both are deleted.

Example 4

Input
s = "mix"
Output
"mix"

There are no brackets to pair, so nothing is deleted.

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is '(' , ')', or a lowercase English letter.

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_remove_to_make_valid(s: str) -> str:
Java
public String minRemoveToMakeValid(String s)

More on the same topics