Minimum Remove to Make Valid Parentheses: Stack Index Pattern

Minimum Remove to Make Valid Parentheses is LeetCode 1249, rated Medium, and it is one of the most practical stack problems you will encounter. The idea is simple: given a string with lowercase letters and parentheses, remove the minimum number of parentheses so that the remaining string is valid. A valid string has every opening parenthesis matched by a closing one, and vice versa.

This problem shows up frequently in interviews because it tests whether you can use a stack to track indices rather than just characters. It is also a building block for more advanced parentheses problems.

Why this problem matters

The pattern of using a stack to validate and fix parentheses strings comes up constantly. Compilers use it to check syntax. Text editors use it to highlight mismatched brackets. Interview problems use it to test your understanding of stack-based matching.

What makes this problem different from basic parenthesis validation is that you are not just checking validity. You are identifying exactly which characters to remove. That requires tracking positions, not just counts. The stack-of-indices technique you learn here applies to a whole family of problems: longest valid parentheses, score of parentheses, remove invalid parentheses, and more.

The key insight

Use a stack to store the indices of unmatched parentheses. When you see a (, push its index. When you see a ), check if the stack has a pending ( on top. If it does, pop it (you found a match). If it does not, the current ) is invalid, so record its index.

After scanning the entire string, anything left on the stack is an unmatched ( that also needs to be removed. Collect all invalid indices into a set, then build the result by including only characters whose indices are not in that set.

The solution

def min_remove_to_make_valid(s):
    stack = []
    invalid = set()

    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        elif ch == ')':
            if stack:
                stack.pop()
            else:
                invalid.add(i)

    invalid.update(stack)

    return ''.join(ch for i, ch in enumerate(s) if i not in invalid)

The first loop handles the scanning. For each character, if it is (, push the index onto the stack. If it is ) and the stack has an unmatched (, pop it to form a matched pair. If the stack is empty when you see ), that closing paren has no partner, so add its index to the invalid set.

After the loop, any indices still on the stack are unmatched ( characters. Add those to the invalid set as well.

The final line builds the output string by keeping only characters at indices not in the invalid set. Because set lookups are O(1), this is a single linear pass.

Visual walkthrough

Let's trace through s = "l(e)e(t(". The stack tracks indices of unmatched ( characters. When a ) arrives and the stack is non-empty, we pop (matched pair). When we finish, anything left on the stack is unmatched and must be removed.

The key moment is the final step. After scanning all eight characters, the stack still holds indices 5 and 7. Those two ( characters never found a matching ), so they get added to the invalid set and excluded from the result. The output is "l(e)et".

Complexity analysis

Time: O(n). You scan the string once to identify invalid indices, then iterate once more to build the result. Both passes are linear.

Space: O(n). The stack can hold up to n/2 indices in the worst case (a string of all ( characters). The invalid set and the output string also use O(n) space.

The building blocks

1. Stack for matching parentheses

The core pattern is: push on open, pop on close. If you cannot pop (stack is empty), the close is unmatched. If the stack is not empty at the end, the remaining opens are unmatched.

stack = []
for i, ch in enumerate(s):
    if ch == '(':
        stack.append(i)
    elif ch == ')':
        if stack:
            stack.pop()

This is the same logic used in Valid Parentheses, Longest Valid Parentheses, and many other stack problems. The only difference between problems is what you do when you find a match or a mismatch.

2. Set-based character removal

Once you know which indices are invalid, build the result by skipping those positions:

invalid = set(indices_to_remove)
result = ''.join(ch for i, ch in enumerate(s) if i not in invalid)

Using a set gives you O(1) lookups per character. This is cleaner than trying to delete characters in place or working with a mutable list, and it avoids off-by-one errors that come from shifting indices after each deletion.

Edge cases

• No parentheses at all: "abc" returns "abc". The stack never gets used, and no indices are marked invalid.
• All parentheses, all unmatched: "(((" returns "". Every index ends up on the stack and gets removed.
• Already valid: "(a)(b)" returns "(a)(b)". Every ( finds a matching ), and the stack is empty at the end.
• Only closing parens: ")))" returns "". Each ) hits an empty stack and gets added to the invalid set.
• Nested valid structure: "((a))" returns "((a))". The stack grows to size 2, then shrinks back to 0 as both ) characters match.
• Mixed invalid on both sides: ")(a)(" returns "(a)". The first ) is invalid (empty stack), the last ( is invalid (never matched).
• Empty string: returns "". Nothing to process.

From understanding to recall

You have seen how the stack collects unmatched indices and how the set-based removal builds the clean result. The logic is clean and the code is short. But will you remember it under time pressure in three weeks?

The tricky parts are small but important: remembering to handle both unmatched ( (left on the stack) and unmatched ) (caught during the scan), using a set for O(1) removal, and building the result with a generator expression. These details are easy to forget if you only solve the problem once.

Spaced repetition locks in the pattern. You practice writing the stack scan from scratch at increasing intervals. After a few rounds, the code flows naturally. You stop second-guessing whether to push the character or the index, whether to check the stack before or after popping, and how to collect the final result.

Related posts

• Valid Parentheses - The foundational stack-based parentheses matching problem
• Minimum Add to Make Parentheses Valid - Counting unmatched parentheses instead of removing them
• Remove Invalid Parentheses - BFS approach to finding all valid strings with minimum removals

CodeBricks breaks this problem into its reusable building blocks, the stack-for-matching pattern and set-based removal, and drills them individually. You type each piece from memory, building the recall so that when you see Minimum Remove to Make Valid Parentheses or any of its variants in an interview, the solution comes without hesitation.