#1249

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Minimum Remove to Make Valid Parentheses

Given a string with parentheses and letters, remove the fewest parentheses to produce any valid balanced string efficiently using a stack.

string stack

Problem Statement

You are given a string s containing lowercase English letters and parentheses '(' and ')'. Your goal is to remove the minimum number of parentheses in any positions so that the resulting string is valid. A valid string has balanced parentheses, meaning each opening parenthesis has a corresponding closing parenthesis and all parentheses are properly nested.

Return any valid string after performing the minimum removals. For example, given s = "lee(t(c)o)de)", removing the extra ')' at the end produces "lee(t(c)o)de". Similarly, s = "a)b(c)d" becomes "ab(c)d", and s = "))((" results in an empty string, which is also valid.

Examples

Example 1

Input: s = "lee(t(c)o)de)"

Output: "lee(t(c)o)de"

"lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2

Input: s = "a)b(c)d"

Output: "ab(c)d"

Example details omitted.

Example 3

Input: s = "))(("

Output: ""

An empty string is also valid.

Constraints

1 <= s.length <= 105
s[i] is either '(' , ')', or lowercase English letter.

Solution Approach

Two-Pass Stack Removal

Use a stack to store indices of '(' as you iterate through the string. When encountering ')', pop a matching '(' from the stack; if none exists, mark ')' for removal. After the first pass, remove all unmatched ')' and leftover '(' from the stack in a second pass to create a valid string.

Single-Pass with Counters

Instead of a full stack, maintain a counter of open parentheses. Increment on '(', decrement on ')'. If decrement would go below zero, skip that ')'. After the pass, iterate backwards to remove extra '(' where the counter is positive. This reduces space while keeping linear time complexity.

String Reconstruction

Mark characters to keep during stack or counter processing and build the final string by joining kept characters. This ensures only necessary removals occur, avoids repeated deletions, and efficiently preserves all lowercase letters in correct order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Both approaches run in O(n) time because each character is processed at most twice. Space is O(n) in the worst-case stack method, or O(1) extra with counters plus the final string, since we store only indices or flags.

What Interviewers Usually Probe

Ask if you can perform removals in-place versus constructing a new string.
Check understanding of prefix balance: no prefix has more ')' than '(' during the first pass.
Probe how the solution scales when nearly all characters are parentheses.

Common Pitfalls or Variants

Common pitfalls

Forgetting to remove unmatched '(' left in the stack after processing all characters.
Assuming the first invalid ')' encountered can be paired later instead of skipped immediately.
Overcomplicating reconstruction by repeated string concatenation instead of using a list or buffer.

Follow-up variants

Return all possible valid strings with minimum removals instead of just one.
Count the minimum number of removals required without returning the actual string.
Apply the same removal logic to multiple types of brackets like '{}', '[]' in addition to '()'.

FAQ

What is the main strategy for Minimum Remove to Make Valid Parentheses?

Use a stack or counter to track open parentheses and remove unmatched ones in two passes, ensuring minimal removals.

Can the solution be done in a single pass?

Yes, using a counter for open parentheses and a backward pass to remove extra '(' allows single-pass logic with efficient reconstruction.

Does the final string need to preserve letter order?

Absolutely, the lowercase letters must remain in their original positions; only parentheses are removed.

What is the time and space complexity?

Time complexity is O(n) since each character is visited at most twice; space is O(n) for a stack or O(1) extra with counters.

Are there common mistakes to avoid?

Yes, forgetting unmatched '(' after processing, skipping prefix balance checks, or repeatedly concatenating strings instead of using a buffer are typical errors.

terminal

Solution

Solution 1: Two Passes

First, we scan from left to right and remove the extra right parentheses. Then, we scan from right to left and remove the extra left parentheses.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stk = []
        x = 0
        for c in s:
            if c == ')' and x == 0:
                continue
            if c == '(':
                x += 1
            elif c == ')':
                x -= 1
            stk.append(c)
        x = 0
        ans = []
        for c in stk[::-1]:
            if c == '(' and x == 0:
                continue
            if c == ')':
                x += 1
            elif c == '(':
                x -= 1
            ans.append(c)
        return ''.join(ans[::-1])

Continue Practicing

#1209 remove all adjacent duplicates in string ii #1190 reverse substrings between each pair of parentheses #1111 maximum nesting depth of two valid parentheses strings