Minimum Remove to Make Valid Parentheses

medium stack strings

Problem

Given a string of '(' , ')' and lowercase letters, remove the minimum number of parentheses so that the result is valid. Return any valid result.

Inputs = "lee(t(c)o)de)"

Output"lee(t(c)o)de"

The trailing ')' has no matching '(', so it is removed.

def min_remove_to_make_valid(s):
    chars = list(s)
    stack = []
    for i, ch in enumerate(chars):
        if ch == '(':
            stack.append(i)
        elif ch == ')':
            if stack:
                stack.pop()
            else:
                chars[i] = ''
    for i in stack:
        chars[i] = ''
    return ''.join(chars)

function minRemoveToMakeValid(s) {
  const chars = s.split("");
  const stack = [];
  for (let i = 0; i < chars.length; i++) {
    if (chars[i] === "(") stack.push(i);
    else if (chars[i] === ")") {
      if (stack.length) stack.pop();
      else chars[i] = "";
    }
  }
  for (const i of stack) chars[i] = "";
  return chars.join("");
}

class Solution {
    public String minRemoveToMakeValid(String s) {
        StringBuilder sb = new StringBuilder(s);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < sb.length(); i++) {
            char c = sb.charAt(i);
            if (c == '(') stack.push(i);
            else if (c == ')') {
                if (!stack.isEmpty()) stack.pop();
                else sb.setCharAt(i, '*');
            }
        }
        while (!stack.isEmpty()) sb.setCharAt(stack.pop(), '*');
        return sb.toString().replace("*", "");
    }
}

string minRemoveToMakeValid(string s) {
    vector<int> stack;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') stack.push_back(i);
        else if (s[i] == ')') {
            if (!stack.empty()) stack.pop_back();
            else s[i] = '*';
        }
    }
    for (int i : stack) s[i] = '*';
    string res;
    for (char c : s) if (c != '*') res += c;
    return res;
}

Explanation

The plan is to find every parenthesis that has no partner and delete just those. A stack of indices lets us pair each ) with the most recent unmatched ( as we scan.

We turn the string into a list chars so we can blank out characters in place. For each ( we push its index. For each ), if the stack has a waiting ( we pop it (a successful match); if the stack is empty, this ) is an orphan, so we erase it by setting chars[i] = ''.

After the scan, any indices still left in the stack are ( that never got closed. We blank those out too. Finally we join the remaining characters into the answer.

Example: s = "lee(t(c)o)de)". The inner ( and ) pairs all match cleanly, but the final ) arrives with an empty stack, so it is removed, giving "lee(t(c)o)de".

It works because the stack guarantees we only delete parentheses that truly lack a match, and that is the minimum number of removals needed to make the string valid.

Time: O(n) Space: O(n)