// Runtime: 0 ms, faster than 100.00% of Java online submissions for Minimum Add to Make Parentheses Valid.
class Solution {
    public int minAddToMakeValid(String S) {
        int balance = 0;
        int fix = 0;

        for (int i = 0; i < S.length(); i++)
            if (S.charAt(i) == '('){
                if (balance > 0) balance++;
                else balance = 1;
            } else {
                balance--;
                if (balance < 0) fix++;
            }

        if (balance > 0) fix += balance;

        return fix;
    }
}