DSA sheet · Stack · Greedy + Stack pattern

Minimum Remove to Make Valid Parentheses

The last problem of the Stack + Greedy pattern. It's a cousin of Minimum Add to Make Parentheses Valid from earlier in the sheet: that one only asked for a count, while this one asks you to return the cleaned-up string. The teacher first explains a brute force (try removing 1 bracket, then 2, …) and why it explodes. Then she builds a stack of indices solution that marks bad brackets with #, and finally a two-pass counter version that drops the stack to save space.

Why it matters: it combines two ideas you'll reuse often. A stack matches each closer with the nearest unmatched opener, and for a single bracket type, a counter can replace the stack.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Stacks from scratch, and the parentheses pattern
• Part A · Brute force: try every set of removals
• Part B · Stack of indices + mark with #
• Part C · Space-optimised: two passes with counters
• Part D · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile: add on the top (push), look at the top (peek), remove from the top (pop). The last thing in is the first thing out: LIFO.

stack = []
stack.append(3)       # push
top = stack[-1]       # peek
x = stack.pop()       # pop
if stack: ...         # empty check: [] counts as False
while stack:          # pop everything that is left
    stack.pop()

Left = bottom, right = top. Never pop or peek without checking that the stack isn't empty, or Python raises IndexError.

The parentheses pattern

A bracket string is valid when every ( has a matching ) after it, and every ) has a matching ( before it. The classic way to check:

• See ( → push it. It's an opener waiting for its partner.
• See ) → if the stack has an opener, pop it: these two are a pair. If the stack is empty, this closer has no partner → invalid.
• At the end, any openers left in the stack never found a closer → invalid.

The stack always pairs a closer with the nearest unmatched opener (the top), which is exactly how nested brackets work: ( ( ) ) pairs inner with inner and outer with outer.

Counter-based space optimisation

When there's only one type of bracket, the stack only ever holds ( characters, all the same. Then we don't need the stack itself, just how many openers are waiting: open += 1 on (, open -= 1 on a matched ). That's O(1) space instead of O(n). (With several bracket types, like ()[]{}, you do need the stack to know which type is on top.)

def is_valid(t):
    open_count = 0
    for ch in t:
        if ch == '(':
            open_count += 1
        elif ch == ')':
            if open_count == 0:      # closer with no partner
                return False
            open_count -= 1
    return open_count == 0           # no opener left waiting

When to think "stack"

The teacher's reminder: whenever you need to go back to check something you saw earlier (a match, a bigger or smaller item), a stack turns that "walk back" from O(n) into O(1).

Part A · Brute force: try every set of removals

LeetCode 1249

1The question in simple words

You get a string with lowercase letters and the brackets ( and ). Remove the fewest brackets so that what's left is valid. Letters are never removed. Return the resulting string (any correct answer is accepted).

LeetCode notes that "lee(t(co)de)" and "lee(t(c)ode)" are also correct; any of them is accepted. Other examples: "a)b(c)d" → "ab(c)d", and "))((" → "" (everything goes).

2What the constraints tell us

• 1 ≤ s.length ≤ 10⁵ → even O(n²) is 10¹⁰. By her rule (past 10⁸ is risky, past 10⁹ is surely TLE) we need about O(n).
• s[i] is (, ), or a lowercase letter → only one bracket type, and there are no other symbols. So we can safely use a symbol like # as a "deleted" marker (Part B), and counters can replace the stack (Part C).

3Intuition: the letters don't matter

Compare the input and output of example 1: every letter is still there, in place. Only the brackets change. So while reading the string, a letter is always kept, and all the thinking is about brackets.

The beginner's way: remove one bracket and check whether the rest is valid. If no single removal works, try every pair of brackets, then every triple, and so on. The first valid string found uses the fewest removals.

4Building the logic

The teacher's point: for "lee(t(c)o)de)" a single removal (the last )) is enough. But on harder strings, no single removal works, then no pair works, and so on, so you end up trying all combinations, because the question doesn't tell you how many brackets to remove. To check each candidate, use the validity check from the Valid Parentheses problem (the counter in Part 0).

5Approach steps

1. List the positions of all brackets.
2. For r = 0, 1, 2, …: for every way to choose r bracket positions to remove →
3. Build the string without them and check is_valid.
4. Return the first valid one (fewest removals).

6Code (Python)

from itertools import combinations

class Solution:
    def minRemoveToMakeValid(self, s):
        brackets = [i for i, ch in enumerate(s) if ch in '()']
        for r in range(len(brackets) + 1):              # how many to remove
            for drop in combinations(brackets, r):      # which ones
                gone = set(drop)
                t = ''.join(ch for i, ch in enumerate(s) if i not in gone)
                if self.is_valid(t):
                    return t
        return ''.join(ch for ch in s if ch not in '()')

    def is_valid(self, t):
        open_count = 0
        for ch in t:
            if ch == '(':
                open_count += 1
            elif ch == ')':
                if open_count == 0:
                    return False
                open_count -= 1
        return open_count == 0

7Code line by line

8Dry run: s = "a)b(c)d"

On "lee(t(c)o)de)" the brute force tries removing the bracket at index 7 before the one at index 12, so it returns "lee(t(co)de)". That's one of the other correct answers LeetCode lists, with the same single removal.

9Complexity & remember

• Time: exponential, about 2ⁿ subsets of brackets, each checked in O(n). With n up to 10⁵ → TLE. The teacher's remark: a brute force can sometimes be this bad.
• Space: O(n) for each candidate string.

Part B · Stack of indices + mark with #

1The question (same)

Remove the minimum number of brackets so the string is valid, in O(n).

2What the constraints tell us

• n ≤ 10⁵ → one or two linear passes.
• Only letters and brackets → # never appears in the input, so it's a safe "removed" mark.

3Intuition

Read left to right. A letter → keep. An opener ( → remember it somewhere, because a closer may need it later. A closer ) → go back and ask "did I save an unused opener?" If yes, the two are a valid pair and both stay. If no, this closer can never be matched, so it must go.

4Building the logic

Why a stack and not a pointer walking back?

You could stand at a closer and move a pointer j backwards, character by character, until you find an unused opener. But the string also has letters (and already-used brackets) in between, so each walk back can cost O(n), making the whole thing O(n²). Storing the openers separately in a stack costs a little extra space but makes "is there an unused opener?" an O(1) look at the top. We spend space to save time.

Every pop "uses up" an opener

In "lee(t(c)o)de)", the first ) pairs with the opener before c, and we pop it. The second ) pairs with the opener before t, and we pop that one too. When the last ) arrives, the stack is empty: both openers are already used. If we didn't pop, two openers would wrongly "match" three closers. Each opener can match only one closer.

Extra openers: the stack must hold indices, not brackets

The teacher's second test: "lee((((t)". Four openers, one closer.

The closer at 8 uses the opener at 6. Openers 3, 4, 5 are still in the stack at the end. A left-to-right pass catches extra closers right away, but extra openers only show up at the end. To remove them we need to know where they are, so we push indices (3, 4, 5, 6), not the "(" characters themselves.

Mark, don't delete

Deleting a character from the middle of a string or array shifts everything after it one step left, which is O(n) per deletion. Instead, turn the string into a list and overwrite bad brackets with #. At the end, build the answer from everything that isn't #. One clean pass.

5Approach steps

1. arr = list(s), stack = [] (it holds indices of waiting openers).
2. For each i: if arr[i] is "(" → push i.
3. If arr[i] is ")": if the stack isn't empty → pop (a valid pair); else → arr[i] = "#".
4. Letters: do nothing.
5. After the loop: pop every leftover index and set arr[index] = "#".
6. Join all characters that aren't "#".

6Code (Python)

class Solution:
    def minRemoveToMakeValid(self, s):
        stack = []                 # indices of '(' still waiting for a partner
        arr = list(s)              # a list we are allowed to change
        for i, ch in enumerate(arr):
            if ch == '(':
                stack.append(i)
            elif ch == ')':
                if stack:
                    stack.pop()    # matched with the nearest waiting '('
                else:
                    arr[i] = '#'   # no partner: mark for removal
        while stack:               # openers that never found a ')'
            arr[stack.pop()] = '#'
        ans = []
        for ch in arr:
            if ch != '#':
                ans.append(ch)
        return ''.join(ans)

7Code line by line

8Dry run

Example 1: s = "lee(t(c)o)de)"

The stack is empty at the end, so no extra openers. Skip the # → "lee(t(c)o)de" ✓

Example 2: s = "lee((((t)" (extra openers)

9Complexity & remember

• Time O(n): one pass over the string, then popping the leftovers (at most n, for example when the string is all openers), then one pass to build the answer. That's O(n) + O(n) + O(n), still linear.
• Space O(n): the stack, the character array and the output. The teacher calls this "a lot of extra space" and asks whether we can do better.

Part C · Space-optimised: two passes with counters

1The question (same)

Same result, but without a stack.

2What the constraints tell us

Only one bracket type → the stack only held "(" anyway. A count of waiting openers carries the same information, like in Minimum Add to Make Parentheses Valid earlier in the sheet.

3Intuition

• Left → right with an open counter: this pass can spot extra closers (a ")" when open is 0).
• But it can't decide which openers are extra. While reading, any opener might still find a closer later. We can't delete one blindly, because we don't know which position to delete.
• So do the mirror pass: right → left with a close counter. From the right, a "(" with no ")" waiting is clearly extra. That removes the extra openers.

4Building the logic on the teacher's example: ")(((le(c))"

Pass 1, left to right (removes extra ")")

Every ")" that's left is needed (removing one would be an extra deletion, and the question asks for the minimum). But open = 2 at the end: two openers are extra. Which two? We can't tell from this pass, so we run the next one.

Pass 2, right to left over "(((le(c))" (removes extra "(")

We collected the kept characters from right to left: ))c(el(. Reverse them → "(le(c))" ✓, which is valid, with 3 removals (1 closer + 2 openers).

5Approach steps

1. Pass 1 (left → right) with open = 0: "(" → keep, open += 1. ")" → keep and open −= 1 only if open > 0, else drop. Letter → keep.
2. Pass 2 (right → left over pass 1's result) with close = 0: ")" → keep, close += 1. "(" → keep and close −= 1 only if close > 0, else drop. Letter → keep.
3. Reverse pass 2's result and join.

6Code (Python)

class Solution:
    def minRemoveToMakeValid(self, s):
        # pass 1: left to right, drop ')' that have no '(' before them
        first = []
        open_count = 0
        for ch in s:
            if ch == '(':
                open_count += 1
                first.append(ch)
            elif ch == ')':
                if open_count > 0:
                    open_count -= 1
                    first.append(ch)
            else:
                first.append(ch)          # letters are always kept

        # pass 2: right to left, drop '(' that have no ')' after them
        ans = []
        close_count = 0
        for ch in reversed(first):
            if ch == ')':
                close_count += 1
                ans.append(ch)
            elif ch == '(':
                if close_count > 0:
                    close_count -= 1
                    ans.append(ch)
            else:
                ans.append(ch)
        ans.reverse()                     # we built it backwards
        return ''.join(ans)

7Code line by line

8Dry run

The two tables in step 4 are the full dry run for ")(((le(c))". On example 1, "lee(t(c)o)de)": pass 1 drops only the last ")" (open is 0 there) and ends with open = 0. Pass 2 keeps everything → "lee(t(c)o)de" ✓.

9Complexity & remember

• Time O(n): two passes (the teacher's O(2n)), plus a reverse. Linear.
• Space: no stack and no marked array, only the strings we build for the answer. The teacher calls it "not more optimised in time, but a little space-optimised". In an interview, give whichever version the interviewer asks for.

Part D · Revision page

s = Solution()
print(s.minRemoveToMakeValid("lee(t(c)o)de)"))   # lee(t(c)o)de
print(s.minRemoveToMakeValid("a)b(c)d"))         # ab(c)d
print(repr(s.minRemoveToMakeValid("))((")))      # ''
print(s.minRemoveToMakeValid("lee((((t)"))       # lee(t)
print(s.minRemoveToMakeValid("(((())))"))        # (((())))
print(s.minRemoveToMakeValid(")(((le(c))"))      # (le(c))

Based on this video: Minimum Remove to Make Valid Parentheses | Stack + Greedy