Minimum Remove to Make Valid Parentheses

Minimum Remove to Make Valid Parentheses is a clean stack question hiding inside a string. You get a string with brackets and letters. Some brackets do not have a partner. Your job is to drop the loose ones and keep everything else. The interviewer wants to see if you can track open brackets and match them as you go.

🎯 The Problem

You get a string with letters and round brackets. You drop the fewest brackets so every one that remains is valid. Valid here means each bracket has a partner.

The rules:

• An open bracket needs a later close bracket.
• A close bracket needs an earlier open bracket.
• Remove the fewest brackets so every remaining bracket has a partner.
• Letters always stay.

For "a)b(c)d", the first ) has no open bracket before it, so it is loose. The ( and the second ) form a real pair, so they stay.

Input:  s = "a)b(c)d"
Output: "ab(c)d"

Explanation: The first ) has no matching ( before it, so we remove it.

Here is which brackets are loose and which form a pair.

🐢 Approach 1: Try Every Removal (Brute Force)

The idea in one line: try every group of removals and keep the smallest one that makes the string valid.

The idea:

• Try removing different sets of brackets.
• Test each result to see if it is valid.
• Keep the smallest removal that works.

How it works:

• Generate every subset of brackets to drop.
• Check each candidate for balance.

Why it is weak:

• The number of ways to pick which brackets to drop grows huge.
• For a long string it becomes impossible to finish.
• Time is exponential. Far too slow.

Here is the brute-force code for that idea:

from collections import deque


def min_remove_to_make_valid(s):
    def valid(text):
        balance = 0
        for ch in text:
            if ch == "(":
                balance += 1
            elif ch == ")":
                balance -= 1
                if balance < 0:
                    return False
        return balance == 0

    queue = deque([s])
    seen = {s}
    while queue:
        text = queue.popleft()
        if valid(text):
            return text
        for i, ch in enumerate(text):
            if ch in "()":
                nxt = text[:i] + text[i + 1:]
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append(nxt)

⚡ Approach 2: A Stack of Indices (Best)

The idea in one line: walk the string once and use a stack of positions to find loose brackets. A stack is a pile where the last thing in is the first thing out.

The idea:

• Keep a stack, but store positions, not the brackets themselves.
• An open bracket pushes its position. It is waiting for a partner.
• A close bracket pairs with the top of the stack, or it is loose.

How it works:

• See an open bracket: push its position onto the stack.
• See a close bracket with the stack not empty: pop. They pair up.
• See a close bracket with an empty stack: mark its position for removal.
• After the pass, anything still on the stack is a loose open bracket, so mark it too.
• Build the answer: walk the string again and skip every marked position.

Why it is fast:

• One pass marks the loose brackets. A second pass builds the answer.
• Each character is touched a constant number of times, so time is O(n).
• Storing positions lets you remove the exact loose bracket later.

Here is a dry run of the stack on the example "a)b(c)d".

Steps to Solve

1. Make an empty stack to hold the positions of open brackets.
2. Make an empty set to hold the positions we must remove.
3. Walk through the string with each character and its position.
4. If it is an open bracket, push its position on the stack.
5. If it is a close bracket, pop a position if the stack has one. If the stack is empty, add this position to the remove set.
6. After the walk, add every position still on the stack to the remove set.
7. Build the answer by keeping every character whose position is not in the remove set.

#include <stdio.h>
#include <string.h>

void minRemove(const char *s, char *out) {
    int n = strlen(s);
    int stack[1000];
    int top = 0;
    int remove[1000] = {0};   // 1 means remove this position
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            stack[top++] = i;          // push the open bracket position
        } else if (s[i] == ')') {
            if (top > 0) top--;        // pair found, pop the open bracket
            else remove[i] = 1;        // no partner, mark this close bracket
        }
    }
    while (top > 0) remove[stack[--top]] = 1;  // leftover open brackets
    int pos = 0;
    for (int i = 0; i < n; i++) {
        if (!remove[i]) out[pos++] = s[i];     // keep unmarked characters
    }
    out[pos] = '\0';
}

int main(void) {
    char out[1000];
    minRemove("a)b(c)d", out);
    printf("%s\n", out);
    return 0;
}

ab(c)d

#include <iostream>
#include <string>
#include <stack>
#include <set>
using namespace std;

string minRemove(string s) {
    stack<int> st;          // positions of open brackets
    set<int> remove;        // positions to drop
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') {
            st.push(i);             // push open bracket position
        } else if (s[i] == ')') {
            if (!st.empty()) st.pop();   // pair found
            else remove.insert(i);       // no partner
        }
    }
    while (!st.empty()) {            // leftover open brackets
        remove.insert(st.top());
        st.pop();
    }
    string result = "";
    for (int i = 0; i < (int)s.size(); i++) {
        if (remove.find(i) == remove.end()) result += s[i]; // keep unmarked
    }
    return result;
}

int main() {
    cout << minRemove("a)b(c)d") << endl;
    return 0;
}

ab(c)d

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

public class MinRemoveParentheses {
    public static String minRemove(String s) {
        Deque<Integer> stack = new ArrayDeque<>();   // open positions
        Set<Integer> remove = new HashSet<>();       // positions to drop
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);              // push open bracket position
            } else if (c == ')') {
                if (!stack.isEmpty()) stack.pop();   // pair found
                else remove.add(i);                  // no partner
            }
        }
        while (!stack.isEmpty()) remove.add(stack.pop()); // leftover opens
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (!remove.contains(i)) result.append(s.charAt(i)); // keep unmarked
        }
        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(minRemove("a)b(c)d"));
    }
}

ab(c)d

def min_remove(s):
    stack = []              # positions of open brackets waiting for a partner
    remove = set()          # positions we will drop
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)         # push the open bracket position
        elif ch == ")":
            if stack:
                stack.pop()         # pair found, remove the open from the stack
            else:
                remove.add(i)       # no open before it, mark this close
    remove.update(stack)            # leftover opens never got a partner
    result = []
    for i, ch in enumerate(s):
        if i not in remove:         # keep every position we did not mark
            result.append(ch)
    return "".join(result)


print(min_remove("a)b(c)d"))

ab(c)d

function minRemove(s) {
  const stack = []; // positions of open brackets
  const remove = new Set(); // positions to drop
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") {
      stack.push(i);          // push open bracket position
    } else if (s[i] === ")") {
      if (stack.length > 0) stack.pop();  // pair found
      else remove.add(i);                 // no partner
    }
  }
  for (const idx of stack) remove.add(idx); // leftover opens
  let result = "";
  for (let i = 0; i < s.length; i++) {
    if (!remove.has(i)) result += s[i];     // keep unmarked
  }
  return result;
}

console.log(minRemove("a)b(c)d"));

ab(c)d

Let us walk through the Python version line by line, because the stack moves are the heart of it.

stack = [] is our pile of open-bracket positions. We use a list because Python lists work as a stack. The append adds to the end and pop takes from the end. That is exactly last in, first out.

remove = set() holds the positions we will drop. A set is good here because we only need to ask “is this position marked?” and a set answers that fast.

for i, ch in enumerate(s): walks the string. The enumerate gives us both the position i and the character ch. We need the position because we are tracking where each loose bracket sits.

if ch == "(": stack.append(i) pushes an open bracket. It is now waiting for a close bracket to partner with. We store its position so we can find it later.

elif ch == ")": handles a close bracket. We check the stack. If stack has something, we pop it, which pairs this close with the most recent open. If the stack is empty, there is no open before this close, so we add(i) to mark it for removal.

remove.update(stack) runs after the walk. Anything still on the stack is an open bracket that never got a close. So all those positions go into the remove set too.

for i, ch in enumerate(s): if i not in remove: builds the answer. We keep every character whose position we did not mark. The check i not in remove is the filter.

return "".join(result) glues the kept characters into one string. We built a list and joined at the end because that is faster than adding to a string over and over.

⏱️ Time and Space Complexity

The brute force tries many removals, so it is far too slow to write down nicely. The stack approach walks the string twice. Once to mark loose brackets, once to build the answer. So it runs in O(n) time, where n is the string length. The stack and the remove set can hold up to n positions, so the extra space is O(n). That is a great trade for a one-pass clean solution.

🧩 Key Takeaways

• ✅ Use a stack to track open brackets waiting for a partner.
• ✅ Store the position of each open bracket, not the bracket itself.
• ✅ A close bracket with an empty stack has no partner, so mark it for removal.
• ✅ Anything left on the stack at the end is a loose open bracket, so remove it too.
• ✅ Build the answer by keeping every position you did not mark.

🚀 What’s Next?

• Valid Word Abbreviation
• Find And Replace in String