409. Brackets to Add
A proofreader receives a line s made only of the characters '(' and ')'. The line is balanced when every opening bracket is matched by a later closing bracket and every closing bracket by an earlier opening one, as in a correct arithmetic formula. The proofreader may insert brackets of either kind at any position, but cannot delete or change existing ones.
Return the smallest number of insertions that makes the line balanced. An empty line is already balanced, so the answer for it is 0. For instance "))(" needs 3 insertions, because both closing brackets lack an opener before them and the last opening bracket lacks a closer. The line can be 100,000 characters long.
Example 1
- Input:
- s = ")(()))("
- Output:
- 3
- Explanation:
The first
)has no partner (1), the group(())is fine, one more)is unmatched (1), and the final(is unmatched (1), so 3 insertions.
Example 2
- Input:
- s = "(()(()"
- Output:
- 2
- Explanation:
Two opening brackets never get closed and nothing is wrongly closed, so 2 insertions are enough.
Constraints
0 ≤ s.length ≤ 105
s[i] is either '(' or ')'.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)