How do you solve Minimum Remove to Make Valid Parentheses?

Convert the string to a list for in-place edits. Iterate through the list, pushing indices of '(' onto a stack. For each ')', pop from the stack if possible; otherwise, mark the ')' for removal by setting it to an empty string. After the iteration, remove all '(' indices remaining in the stack by setting those positions to empty strings. Finally, join the list into a string and return it.

Minimum Remove to Make Valid Parentheses

Q: What is the time complexity of Minimum Remove to Make Valid Parentheses?

O(n). The algorithm makes a single pass through the string to identify invalid parentheses and a second pass to remove unmatched openings, each operation being O(1) per character, resulting in O(n) total time.

Q: What pattern does Minimum Remove to Make Valid Parentheses use?

The Pattern: Stack (Parentheses Matching) The Heuristic: Use a stack to track indices of unmatched opening parentheses. Unmatched closing parentheses are identified immediately and removed, and any remaining unmatched opening parentheses are removed after processing, ensuring minimal removals for validity.

Medium Monotonic Stack

Problem

Given a string s containing parentheses and lowercase English letters, return a string after removing the minimum number of parentheses to make the input string valid. A string is valid if parentheses are balanced and properly closed.

1 ≤ s.length ≤ 10⁵
s[i] is either '(', ')', or a lowercase English letter.

Example

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

Output: "ab(c)d"

Walk through the string from left to right: Index 0: 'a' -> not a parenthesis, keep it. Index 1: ')' -> the stack is empty, so there is no matching '('. Mark this ')' for removal by setting s[1] = "". Index 2: 'b' -> keep it. Index 3: '(' -> push index 3 onto the stack. Index 4: 'c' -> keep it. Index 5: ')' -> the stack is not empty, so we pop 3 from the stack and treat this as a matched pair. Keep this ')'. Index 6: 'd' -> keep it. After this pass, any indices left in the stack would be unmatched '(' positions (none in this example). We then mark those for removal as well. Finally, we join the characters that were not cleared out, which gives "ab(c)d", a valid parentheses string with the minimum removals.

Approach

Straightforward Solution

A brute-force approach might try all subsets of characters to find the minimal removal that yields a valid string, which is exponential and infeasible for large inputs.

Core Observation

A valid parentheses string requires every '(' to be matched with a corresponding ')' in the correct order. Unmatched parentheses must be removed to achieve validity.

Path to Optimal

Preview

The key insight is to use a stack to track indices of unmatched '(' characters. When encountering a ')', if the stack is empty, this ')' is unmatched and must be removed…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Convert the string to a list for in-place edits. Iterate through the list, pushing indices of '(' onto a stack…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm makes a single pass through the string to identify invalid parentheses and a second pass to remove unmatched openings, each operation being O(1) per character, resulting in O(n) total time.

Space

O(n)

The stack can hold up to O(n) indices in the worst case (all '(' characters). The string is converted to a list of characters, which is O(n) auxiliary space excluding the input and output.

Pattern Spotlight

Stack (Parentheses Matching)

Use a stack to track indices of unmatched opening parentheses. Unmatched closing parentheses are identified immediately and removed, and any remaining unmatched opening parentheses are removed after processing, ensuring minimal removals for validity.

Solution

Python

1class Solution:
  def minRemoveToMakeValid(self, s: str) -> str:
      s = list(s)
      stack = []
      for i, c in enumerate(s):
          if c == '(':
              stack.append(i)
          elif c == ')':
              if stack:
                  stack.pop()
              else:
                  s[i] = ''
13
      while stack:
          s[stack.pop()] = ''
      return ''.join(s)

Step-by-Step Solution

Convert String to List and Initialize Stack for Tracking

3s = list(s)
4stack = []

Objective

To prepare the input for in-place modifications and set up a data structure to track unmatched opening parentheses indices.

Key Insight

Strings in many languages are immutable, so converting to a list allows marking invalid characters by replacing them with empty strings without rebuilding the string repeatedly. The stack stores indices of '(' characters, enabling efficient matching with ')' characters during iteration.

Interview Quick-Check

Core Logic

Converting the string to a list allows O(1) time marking of invalid characters, avoiding costly string concatenations.

State & Boundaries

The stack holds indices of '(' characters that are unmatched so far.

Common Pitfalls & Bugs

Forgetting to convert the string to a mutable structure leads to inefficient or incorrect removal of characters.

Iterate Through Characters to Identify Invalid Parentheses

To scan the string and use the stack to match parentheses, marking unmatched closing parentheses for removal.

Remove Remaining Unmatched Opening Parentheses and Rebuild String

To remove all unmatched '(' characters left on the stack and return the valid string.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 7 Critical

stack.append(i)

Push the index of '(' onto the stack.

This line is critical because it records the position of an unmatched '(' to enable correct pairing or removal later, forming the backbone of the stack-based matching algorithm.

Line 9 Critical

if stack:

Check if there is an unmatched '(' available to match with the current ')'.

This check is crucial to avoid invalid matches and to identify unmatched ')' that must be removed, preserving correctness.

Line 12 Critical

s[i] = ''

Mark the unmatched ')' for removal by replacing it with an empty string.

This line's placement is critical to immediately mark unmatched ')' for removal, ensuring minimal removals and preserving the original string structure for subsequent processing.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why is it necessary to remove unmatched opening parentheses after processing the entire string rather than during the initial iteration?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Minimum Remove to Make Valid Parentheses from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Minimum Remove to Make Valid Parentheses drill

or drill a free problem

1	`class Solution:`
2	`def minRemoveToMakeValid(self, s: str) -> str:`
3	`s = list(s)`
4	`stack = []`
5	`for i, c in enumerate(s):`
6	`if c == '(':`
7	`stack.append(i)`
8	`elif c == ')':`
9	`if stack:`
10	`stack.pop()`
11	`else:`
12	`s[i] = ''`
13
14	`while stack:`
15	`s[stack.pop()] = ''`
16	`return ''.join(s)`