Remove the fewest parentheses from a string so that the remaining string is valid.
Given a string containing lowercase English letters and parentheses ( and ), remove the minimum number of parentheses so that the resulting string is valid.
A string is valid if:
- Every opening parenthesis
(has a matching closing parenthesis). - Parentheses are properly nested.
- Non-parenthesis characters may remain anywhere in the string.
Return any valid string that can be obtained by removing the minimum number of parentheses.
Input Format
- A single string
sconsisting of lowercase letters and the characters(and).
Output Format
- Return one string formed by removing the minimum number of parentheses from
sso that it becomes valid.
Constraints
scontains only lowercase English letters,(, and).- The answer is guaranteed to exist.
Example 1
Input
s = "lee(t(c)o)de)"
Output
"lee(t(c)o)de"
Explanation
The last ) is unmatched, so removing it makes the string valid.
Example 2
Input
s = "a)b(c)d"
Output
"ab(c)d"
Explanation
Remove the unmatched ) near the beginning.
Show 1 more example
Example 3
Input
s = "))(("Output
""
Explanation
All parentheses must be removed to make the string valid.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.