Fix unbalanced parentheses: A Sample Coding Interview Solution

The coding question

Given a string with letters and parentheses, remove the fewest parentheses so the result is valid, and return any valid result.

Ask a few questions first

Ask	What we'll assume
Which characters can show up?	Lowercase letters, ( and ). No other bracket types.
Should letters ever be removed?	No, only parentheses.
If there are several right answers, which one?	Any valid one with the fewest removals.
How long can the string be?	Up to about 100,000 characters, so it should be linear.

A couple of examples

Input	Output
"lee(t(c)o)de)"	"lee(t(c)o)de"
"a)b(c)d"	"ab(c)d"
"))(("	"" (empty string)

Start with brute force

Try removing 0 parentheses, then every way of removing 1, then every way of removing 2, and so on, checking each result. The first valid one you find uses the fewest removals.

Cost: Exponential: with k parentheses there are 2 to the k ways to choose which to remove. Hopeless for long strings.

A better way

A ) is bad exactly when there's no earlier unmatched ( for it to close. A ( is bad exactly when nothing later closes it. Every other bracket can stay.

So walk left to right, keeping a stack of the positions of open brackets that haven't been matched yet. A ) pops one if there is one, and gets removed if there isn't. Whatever's left on the stack at the end are the opens that never got closed. Remove those too.

Turn the string into a list of characters so you can blank some out.
Walk through it. On (, push its index onto a stack.
On ), pop the stack if it isn't empty. If it is, blank out this ).
After the loop, blank out every index still on the stack.
Join the list back into a string.

The code

solution.pypython

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

	Cost	Why
Time	O(n)	One pass, plus one pass over the leftover opens
Space	O(n)	The list of characters and the stack

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

Empty string: returns "".
No parentheses, like "abc": returns it unchanged.
Only opens, like "(((": all removed, giving "".
Already valid, like "()()": unchanged.
Wrong way round, like ")(a)(": the first ) and the last ( go, giving "(a)".

Common mistakes

Building the answer with string += in a loop. In some languages that's O(n squared). Use a list and join once.
Only counting opens and closes without tracking positions, so you know how many to remove but not which ones.
Removing extra ( from the front instead of the ones that were actually unmatched, which can break a valid pair.

Follow-up questions

Can you do it without the stack?

Yes. Walk left to right with a counter of open brackets, dropping any ) when the counter is 0. Then walk right to left with a counter of closes, dropping extra (. O(1) extra space apart from the output.

What if you need every valid result with the fewest removals?

That's a different problem. Use BFS over strings with one bracket removed at a time, and stop at the first level that has any valid strings.

What about [] and {} too?

Push the bracket type with its index, and only pop when the closing type matches. A mismatch needs a decision about which one to drop, so ask what the interviewer wants.

How the time adds up

Minutes	What you're doing
0–2	Clarify. Keep it short: Meta usually wants two problems in about 45 minutes, so this one gets about 20
2–4	Brute force and why it blows up
4–8	Explain which brackets are unmatched and the stack
8–15	Write the code
15–18	Walk through an example and the edge cases
18–20	Follow-up questions

Key concepts used here

Stacks and monotonic stacksMatch brackets, parse things, and find the next bigger value in one pass.

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Meta.