// Runtime: 0 ms, faster than 100.00% of Java online submissions for Minimum Add to Make Parentheses Valid.
// Memory Usage: 34.3 MB, less than 100.00% of Java online submissions for Minimum Add to Make Parentheses Valid.

class Solution {
    public int minAddToMakeValid(String S) {
        char[] chars = S.toCharArray();

        int left = 0;
        int right = 0;
        for (char ch : chars) {
            if(ch == '(') {
                left++;
            } else {
                if(left > 0) {
                    left--;
                } else {
                    right++;
                }
            }
        }

        return left + right;
    }
}