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 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.

Complexity Analysis

  • Time Complexity: , where is the length of S.

  • Space Complexity: .


Analysis written by: @awice.