[Leetcode] 1249. Minimum Remove to Make Valid Parentheses

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

initial

actually i found it v simple but there is even cleaner approach. We know strings in py are immutable while lists are mutable. So we first change it to list

we store the indexes of OPEN brackets in stack. If we see a closed bracket we pop that open bracket idnex cuz its a valid pair. But if we have excess closed brackets (ie. stack is empty) then we can mark the value at that specific index as empty string (""). If we have excess open brackets stored in stack, as we pop those indexes we also mark that index as empty string

sol

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        lst = list(s)
        stack=[]
        for i,val in enumerate(lst):
            if val=="(":
                stack.append(i)
            elif val==")":
                if stack:
                    stack.pop()
                else:
                    lst[i]=""
            else:
                continue
        while stack:
            idx = stack.pop()
            lst[idx]=""
        return ''.join(lst)

java

same idea but here instead of list, use char array to be more eff

import java.util.*;

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stack = new Stack<>();
        char[] chars = s.toCharArray(); // Use array instead of List for O(1) access
        
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                stack.push(i);
            } else if (chars[i] == ')') {
                if (stack.isEmpty()) {
                    // Mark this ')' for removal
                    chars[i] = '*'; 
                } else {
                    stack.pop();
                }
            }
        }
        
        // Any '(' left in the stack are unmatched
        while (!stack.isEmpty()) {
            chars[stack.pop()] = '*';
        }
        
        // Build the final string, skipping the '*' markers
        StringBuilder ans = new StringBuilder();
        for (char c : chars) {
            if (c != '*') {
                ans.append(c);
            }
        }
        
        return ans.toString();
    }
}

complexity

n time
n space