Minimum Add to Make Parentheses Valid

Share

Given a string s of ( and ) characters, return the minimum number of parentheses to add to make the string valid (every opening has a matching closing and vice versa).

Example 1
Input: "())" → Output: 1
Example 2
Input: "(((" → Output: 3

Solution Approach

Track unmatched open and unmatched close parentheses. Scan left to right: increment open count for (, for ) either decrement open if open>0 or increment close count.

  • open = unmatched open brackets, close = unmatched close brackets.
  • For each char: if ( increment open.
  • If ): if open > 0, decrement open (matched); else increment close.
  • Answer = open + close.
Java
class Solution {
    public int minAddToMakeValid(String s) {
        int open = 0, close = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') open++;
            else if (open > 0) open--;
            else close++;
        }
        return open + close;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(1)