420. Fewest Bracket Removals
A code formatter is given a line containing lower-case letters, opening brackets ( and closing brackets ). It may only delete bracket characters, never letters, and it wants the result to have every bracket properly matched: each ( is closed by a later ) and no ) appears without an open partner.
Return a string that can be produced from s by deleting the smallest possible number of brackets and that is valid in the sense above. Several different results may exist; any one of them is accepted. The judge checks that your string is valid, is a subsequence of s, and has the largest possible length.
Example 1
- Input:
- s = "pa(ni)c)k(e"
- Output:
- "pa(ni)cke"
- Explanation:
The final ) has no partner, and the last ( is never closed. Removing exactly those two brackets gives pa(ni)cke; the letters stay in order.
Example 2
- Input:
- s = "))g(h)(("
- Output:
- "g(h)"
- Explanation:
The two leading ) and the two trailing ( cannot be matched; deleting them leaves g(h).
Constraints
1 ≤ s.length ≤ 100000s contains only lower-case English letters, '(' and ')'.
How this problem is judged
- Answers
- Any valid answer is accepted. A checker tests yours against the problem's rules.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)