Stack - Minimum Add to Make Parentheses Valid

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

Input: "())" → Output: 1

Input: "(((" → Output: 3

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.

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)