Skip to content
Onsite
24 / 28

Minimum Remove to Make Valid Parentheses

MediumP2Coding

Given a string s of lowercase letters and the parentheses ( and ), remove the fewest parentheses so that the parentheses become balanced, and return the resulting string. Letters are never removed.

To make the answer unique, match parentheses in the usual way: each ) pairs with the nearest earlier ( that is still unmatched. Remove exactly the parentheses that end up unmatched.

Example 1

Input
s = "lee(t(c)o)de)"
Output
"lee(t(c)o)de"
Why
The last ) has no partner.

Example 2

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

Example 3

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

Constraints

  • 1 <= s.length <= 10^5
  • s has lowercase letters, '(' and ')'

Hints

Run checks the 3 visible tests, Submit all 12.