Solution
Approach 1: Balance
Intuition and Algorithm
Keep track of the balance of the string: the number of '('
's minus the number of ')'
's. A string is valid if its balance is 0, plus every prefix has nonnegative balance.
The above idea is common with matching brackets problems, but could be difficult to find if you haven't seen it before.
Now, consider the balance of every prefix of S
. If it is ever negative (say, 1), we must add a '(' bracket. Also, if the balance of S
is positive (say, +B
), we must add B
')' brackets at the end.
Complexity Analysis

Time Complexity: , where is the length of
S
. 
Space Complexity: .
Analysis written by: @awice.