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

class Solution {
    public int minAddToMakeValid(String S) {
        return countMissingOpenBrackets(S) + countMissingOpenBracketsBackwards(S);
    }

    int countMissingOpenBrackets(String s) {
        int open = 0;
        int result = 0;
        for(int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                open++;
            } else if (s.charAt(i) == ')') {
                if(open > 0) open--;
                else result++;
            }
        }
        return result;
    }


    int countMissingOpenBracketsBackwards(String s) {
        int open = 0;
        int result = 0;
        for(int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == ')') {
                open++;
            } else if (s.charAt(i) == '(') {
                if(open > 0) open--;
                else result++;
            }
        }
        return result;
    }
}