1249. Minimum Remove to Make Valid Parentheses

Practice Minimum Remove to Make Valid Parentheses for free on NudgeCode: Medium, Stack pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

s contains lowercase letters and the characters ( and ). Delete as few parentheses as possible so that the parentheses left over are balanced, and return the resulting string. Letters must stay, in their original order.

In general several results can be valid. Every test here is built so that only one valid result exists.

Example

s = "a)b(c)d"  ->  "ab(c)d"
s = "))(("     ->  ""
s = "())"      ->  "()"

Constraints

• 1 <= s.length <= 10^5
• s contains only lowercase English letters, ( and )