[LeetCode] 1249. Minimum Remove to Make Valid Parentheses

 Problem : https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/

Instead of using stack, this is more like a greedy algorithm.

Scan the input string 2 times.  

The 1st time scan, find the total number of valid left and right parentheses.

The 2nd time scan, greedily add the valid left and right parentheses. 

Please be noticed, we cannot add right-parenthesis if there is no corresponding left-parenthesis be added before.

class Solution {
    public String minRemoveToMakeValid(String s) {
        char[] buffer = s.toCharArray();
        
        // find total number valid parentheses 
        int unmatchedLeft = 0;
        int validLeft = 0;
        int validRight = 0;
        
        for (char c : buffer) {
            if (c == '(') {
                unmatchedLeft += 1;
            } else if (c == ')') {
                if (unmatchedLeft > 0) {
                    unmatchedLeft -= 1;
                    
                    validLeft += 1;
                    validRight += 1;
                }
            }
        }
    
        // greedily add valid parentheses
        StringBuilder sb = new StringBuilder();
        int left = 0;
        int right = 0;
        
        for (char c : buffer) {
            if (c == '(' && left >= validLeft) {
                continue;
            }
            
            // cannot add right-parenthesis 
            // if there is no corresponding left-parenthesis be added before
            if (c == ')' && ( right >= validRight || left == right)) {
                continue;
            }
            
            sb.append(c);
            
            if (c == '(') {
                left += 1;
            } else if (c == ')') {
                right += 1;
            }
        }
        
        return sb.toString();
    }
}