427. Peel Outer Brackets
A balanced bracket string can be cut into primitive blocks: a block is a balanced piece that cannot itself be split into two non-empty balanced pieces, such as () or (()()). Reading s from left to right, the blocks appear one after another and together make up the whole string exactly once.
Remove the outermost pair of brackets from every primitive block, that is, delete the first '(' and the matching last ')' of each block, then glue what is left of all the blocks together in their original order and return the result. A block like () disappears completely. The input is always a balanced string of at most 100,000 characters (possibly empty).
Example 1
- Input:
- s = "(()())((()))()"
- Output:
- "()()(())"
- Explanation:
The blocks are
(()()),((()))and(). Peeling gives()(),(())and nothing, joined as()()(()).
Example 2
- Input:
- s = "((())())(())"
- Output:
- "(())()()"
- Explanation:
The blocks are
((())())and(()); peeling gives(())()and(), so the result is(())()().
Constraints
0 ≤ s.length ≤ 105
s is a balanced string made of '(' and ')' only.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(n)