MediumStringStackUpdated Sep 2026

1249. Minimum Remove to Make Valid Parentheses

Asked at Meta

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

String

Companies

1

Problem

You are given a string s made of lowercase letters and the two characters ( and ). Some of the parentheses do not match up. Delete the smallest possible number of parentheses so that what is left is a valid parentheses string, and return that result.

A string is valid when every ) has an ( before it that is still open, and no ( is left without a closing ). Letters are always fine and never need to be removed. You may return any valid string that uses the minimum number of removals.

Only parentheses are ever deleted. The letters keep their original order, and the remaining parentheses keep their order too.

Which parentheses are broken?

lee(t(c)o)de)0123456789101112Index 11 is the unmatched ')' — the only character we drop
Scanning left to right, the final ')' has no open '(' waiting for it, so it must be removed.

Constraints

  • ●1 <= s.length <= 10^5
  • ●s[i] is either '(', ')', or a lowercase English letter

Examples

Example 1
Inputs = "lee(t(c)o)de)"
Output"lee(t(c)o)de"
WhyThe last `)` has no partner, so we drop it. Everything else already matches, so the result is valid and only 1 character was removed.
Example 2
Inputs = "a)b(c)d"
Output"ab(c)d"
WhyThe `)` right after `a` has no open `(` before it, so it must go. The pair `(c)` is fine, so we keep it.
Example 3
Inputs = "))(("
Output""
WhyThe two `)` come before any `(`, and the two `(` are never closed. All four characters are unmatched, so removing all of them leaves the empty string, which is valid.

Asked At

1 companies
CompanyDifficulty
MetaMediumView all Meta questions →

How to Think About It

1

Brute force: generate all subsets of characters and check validity — O(2^n).

2

Use a stack to track unmatched opening parentheses as you scan left to right.

3

Mark indices of unmatched parentheses for removal.

4

First pass: find unmatched '(' by counting open > close. Second pass: remove excess '(' from the right.

5

Combine both passes: remove unmatched '(' and unmatched ')' in a single string construction.

Optimal Approach

Perform two passes. First pass: scan left to right, tracking open count. Any ')' that appears when open is zero is marked for removal. After the first pass, any remaining open count means we have unmatched '(' — mark the rightmost unmatched '(' for removal. Build the result string by skipping marked indices. This runs in O(n) time with O(n) space.

Two passes: mark, then rebuild

lee(t(c)o)de)0123456789101112open=1open=2open=1open=0Pass 1 — open goes 1,2,1,0; the last ')' arrives with open=0, so mark itlee(t(c)o)de01234567891011Pass 2 — skip the marked index and keep everything else')' with open == 0 → removeleftover open > 0 → remove that many '(' from the right
Pass 1 finds unmatched ')' and counts leftover '('. Pass 2 drops those ')' and the rightmost leftover '('.
ComplexityTime O(n)Space O(n)We scan the string twice, and the set of removed indices plus the output buffer can each hold up to n entries.

What Trips People Up in Real Interviews

1

Clarify that non-parenthesis characters should always be kept.

2

Edge case: empty string returns empty string.

3

Edge case: no parentheses at all returns the original string.

4

Walk through "lee(t(c)o)de)" to show both removals.

5

Mention two-pass approach: first remove unmatched ')', then unmatched '('.

Solution Code

O(n) time
def minRemoveToMakeValid(s: str) -> str:
    indices_to_remove = set()
    open_count = 0
    for i, ch in enumerate(s):
        if ch == '(':
            open_count += 1
        elif ch == ')':
            if open_count == 0:
                indices_to_remove.add(i)
            else:
                open_count -= 1
    stack = []
    for i, ch in enumerate(s):
        if ch == '(' and open_count > 0:
            open_count -= 1
            continue
        if i not in indices_to_remove:
            stack.append(ch)
    return ''.join(stack)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Minimum Remove to Make Valid Parentheses problem?

Given a string containing lowercase English letters, parentheses, and possibly other characters, remove the minimum number of invalid parentheses to make the input string valid. Return any valid result.

How do you solve Minimum Remove to Make Valid Parentheses?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Minimum Remove to Make Valid Parentheses?

Minimum Remove to Make Valid Parentheses is asked at Meta. It is a medium difficulty problem.

What are common mistakes on Minimum Remove to Make Valid Parentheses?
  • Clarify that non-parenthesis characters should always be kept.
  • Edge case: empty string returns empty string.
  • Edge case: no parentheses at all returns the original string.
  • Walk through "lee(t(c)o)de)" to show both removals.
  • Mention two-pass approach: first remove unmatched ')', then unmatched '('.