Minimum Remove to Make Valid Parentheses
MediumStack · Meta
You are given a string s made of lowercase English letters and the characters ( and ).
Delete the smallest possible number of parentheses so that the remaining string is valid, and return the result. Letters are never deleted, and the characters you keep stay in their original order.
A string is valid when, reading left to right, the number of ) seen so far never exceeds the number of ( seen so far, and the two counts are equal at the end. Letters do not affect validity, and a string with no parentheses (including the empty string) is valid.
If several results need the same minimum number of deletions, return any one of them.
Example 1
- Input:
- s = "x(y)z)(w"
- Output:
- "x(y)zw"
- Explanation
- The
)afterzhas no(left to match, and the final(is never closed. Deleting just those two gives a valid string with every letter kept.
Example 2
- Input:
- s = "())()((("
- Output:
- "()()"
- Explanation
- The second
)is unmatched, and so are the three trailing(. Four deletions are needed; any valid result of that length that keeps the remaining characters in order is accepted.
Example 3
- Input:
- s = "abc(d)e)"
- Output:
- "abc(d)e"
- Explanation
- Only the last
)is unmatched, so it is the single character deleted.
Constraints
- 1 ≤
s.length≤ 105 scontains only lowercase English letters,(, and)