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 non-negative 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.
Time Complexity: , where is the length of
Space Complexity: .
Analysis written by: @awice.