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:
( has a matching closing parenthesis ).Return any valid string that can be obtained by removing the minimum number of parentheses.
s consisting of lowercase letters and the characters ( and ).s so that it becomes valid.s contains only lowercase English letters, (, and ).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.
Example 3
Input
s = "))(("Output
""
Explanation
All parentheses must be removed to make the string valid.
Premium problem context
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.