A string s contains lowercase letters, ( and ). Remove every unmatched bracket and return the result:
- a
)is unmatched if, reading left to right, there is no earlier(still waiting for a partner; - a
(is unmatched if it never receives a partner by the end of the string.
Letters are always kept.
Examples
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Input: s = "a)b(c)d"
Output: "ab(c)d"
Input: s = "))(("
Output: ""
Constraints
0 <= len(s) <= 10**5- Target:
O(n)time
Goals
- Record the positions of brackets, not just their counts
- Rebuild a string while skipping a set of indices