Minimum Remove to Make Valid Parentheses

Minimum Remove to Make Valid Parentheses

What is this problem about?

The Minimum Remove to Make Valid Parentheses problem gives you a string containing lowercase letters and parentheses. Your task is to remove the minimum number of parentheses so that the resulting string is valid — meaning every open bracket has a matching close bracket in the correct order. This Minimum Remove to Make Valid Parentheses coding problem is a staple of stack-based string manipulation.

Why is this asked in interviews?

This problem is a favorite at Meta, Apple, Amazon, Netflix, Google, Microsoft, and Bloomberg because it directly tests stack usage for bracket matching — a fundamental pattern that appears across compilers, expression evaluators, and code formatters. The string and stack interview pattern is cleanly demonstrated, and the problem has a satisfying, elegant solution that interviewers love to see candidates arrive at naturally.

Algorithmic pattern used

The approach uses a stack to track unmatched indices. Traverse the string: push the index of every '(' onto the stack. When you encounter ')', pop from the stack if it's non-empty (a match is found). If the stack is empty for ')', mark this ')' for removal. After the traversal, any indices remaining in the stack are unmatched '(' — mark them too. Build the result string by skipping all marked indices.

Example explanation

String: "a(b(c)d)".

• Index 1: '(' → push 1.
• Index 3: '(' → push 3.
• Index 4: ')' → pop 3 (matched with index 3).
• Index 6: ')' → pop 1 (matched with index 1). Stack is empty. No removals needed. Result: "a(b(c)d)" — already valid.

String: "a)b(":

• Index 1: ')' → stack empty, mark index 1.
• Index 3: '(' → push 3. After traversal, index 3 remains in stack, mark it. Result: "ab".

Common mistakes candidates make

• Removing characters in-place during traversal, which causes index shifts.
• Not handling the characters remaining in the stack after the full pass.
• Using a boolean array instead of a set for marking, which can be error-prone.
• Forgetting that letters (non-parentheses) are always kept.

Interview preparation tip

Minimum Remove to Make Valid Parentheses is an excellent problem to rehearse two-pass stack techniques. In the first pass, identify invalid indices; in the second pass, build the result. This two-pass approach is cleaner than trying to reconstruct in a single pass. Practice explaining your stack-usage reasoning aloud — interviewers value clear verbal articulation for stack problems, which can otherwise feel tricky to describe.