1249_Min_remove_to_make_valid_parenthesis

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

// APPROACH 2
class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        String[] arr = s.split("");
        for (int i=0; i<arr.length; i++) {
            if (arr[i].equals("("))
                stack.push(i);
            if (arr[i].equals(")")) {
                if (!stack.isEmpty())
                    stack.pop();
                else
                    arr[i] = "";
            }
        }
        while (!stack.isEmpty())
            arr[stack.pop()] = "";
        return String.join("",arr);
    }
}

// APPROACH 1
// class Solution {
//     public String minRemoveToMakeValid(String s) {
//         StringBuilder sb = new StringBuilder(s);
//         Stack<Integer> stack = new Stack<Integer>();
//         for (int i=0; i<sb.length(); i++) {
//             if (sb.charAt(i) == '(')stack.add(i);
//             if (sb.charAt(i) == ')') {
//                 if (!stack.isEmpty())
//                     stack.pop();
//                 else
//                     sb.setCharAt(i, '*');
//             }
//         }
//         while (!stack.isEmpty())
//             sb.setCharAt(stack.pop(),'*');
//         return sb.toString().replaceAll("\\*","");
//     }
// }

// MY APPROACH - FAILED
// class Solution {
//     public String minRemoveToMakeValid(String s) {
//         Stack<Character> stack = new Stack<Character>();
//         int left = 0;
//         String ans = "";
//         for (char ch : s.toCharArray()) {
//             if (Character.isLetter(ch)) 
//                 ans += ch;
//             else {                   
//                 if (ch == '(') {
//                     ans += ch;
//                     stack.push(ch);
//                 }
//                 else {
//                     if (!stack.isEmpty() && stack.pop() == '(')
//                         ans += ch;
//                 }
//             }
//         }
        
//         return ans;
//     }
// }