MinRemoveToMakeValid.java

class MinRemoveToMakeValid {

    public String minRemoveToMakeValid(String s) {

        /*
        Runtime: 17 ms, faster than 92.16% of Java online submissions for Minimum Remove to Make Valid Parentheses.
Memory Usage: 42.8 MB, less than 95.25% of Java online submissions for Minimum Remove to Make Valid Parentheses.
        */
        // Pass 1: Remove all invalid ")"
        StringBuilder sb = new StringBuilder();
        int openSeen = 0;
        int balance = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                openSeen++;
                balance++;
            } if (c == ')') {
                if (balance == 0) continue;
                balance--;
            }
            sb.append(c);
        }

        // Pass 2: Remove the rightmost "("
        StringBuilder result = new StringBuilder();
        int openToKeep = openSeen - balance;
        for (int i = 0; i < sb.length(); i++) {
            char c = sb.charAt(i);
            if (c == '(') {
                openToKeep--;
                if (openToKeep < 0) continue;
            }
            result.append(c);
        }

        return result.toString();
    }
}