All problems

Minimum Remove to Make Valid Parentheses

Medium · stack

You are given a string s made of lowercase letters and the brackets ( and ).

Pair up the brackets like this. Read s from left to right. Each ) is paired with the closest ( to its left that has not been paired yet. If there is no such (, that ) stays unpaired. Any ( that is never paired is unpaired as well.

Remove every unpaired bracket and return the string that is left. Letters are never removed. The result has balanced brackets, and no result with balanced brackets removes fewer brackets.

Examples

Example 1

Input: s = "x(y)z)"

Output: "x(y)z"

The first ) pairs with the ( before it. The final ) has no ( left to pair with, so it is removed.

Example 2

Input: s = "(a(b)c"

Output: "a(b)c"

The ) pairs with the closest ( on its left, the one before b. The ( at the very start never gets a partner and is removed.

Example 3

Input: s = "))(("

Output: ""

No ( comes before either ), and the two ( have no ) after them, so every bracket is removed.

Constraints

• 1 <= len(s) <= 10^4
• s contains only lowercase letters, ( and )