Parentheses / Matching

Min Remove to Make Valid

First pass: use a stack to find indices of unmatched parentheses. Second pass: rebuild the string skipping those indices. This gives you the string with minimum removals to make parentheses valid.

O(n)

How It Works

To make a parentheses string valid with the fewest deletions, identify exactly which characters are unmatched — everything else can stay. First pass: scan with a stack of indices. Push the index of every '('; on ')', pop a match if one exists, otherwise mark that ')' index for removal. When the scan ends, any indices still on the stack are unmatched '(' characters and are marked too. Second pass: rebuild the string, skipping marked indices.

This is O(n) time and O(n) space, and it is provably minimal: every marked character has no possible partner, so no valid result can keep it, and keeping all unmarked characters yields a valid string.

Step-by-Step Visualization

Remove min parens to make valid: 'le(e)t((cod)e)'

Input

(

)

(

)

Stack (empty)

ScanFind unmatched

1/4

Code

Java

static String minRemoveToMakeValid(String s) {
  Stack<Integer> stack = new Stack<>();
  Set<Integer> remove = new HashSet<>();

  for (int i = 0; i < s.length(); i++) {
    if (s.charAt(i) == '(') stack.push(i);
    else if (s.charAt(i) == ')') {
      if (!stack.isEmpty()) stack.pop();
      else remove.add(i);
    }
  }
  while (!stack.isEmpty()) remove.add(stack.pop());

  StringBuilder sb = new StringBuilder();
  for (int i = 0; i < s.length(); i++)
    if (!remove.contains(i)) sb.append(s.charAt(i));
  return sb.toString();
}

Tips & Gotchas

1First pass: use stack to find unmatched parentheses indices

2Second pass: build result string skipping those indices

3Track indices, not the characters themselves

Practice Problems

1Minimum Remove to Make Valid Parentheses
2Minimum Add to Make Parentheses Valid
3Remove Invalid Parentheses

About the Parentheses / Matching Pattern

Stacks naturally handle nested structures. Push opening symbols, pop when you find their closing match. If the stack is empty at the end and every match was correct, the expression is valid.

Key insight

Monotonic stacks are the power tool here. If you need 'next greater/smaller element' or 'span' queries, a monotonic stack gives O(n) instead of O(n²).

Common Stack Interview Problems

Valid Parentheses
Next Greater Element
Largest Rectangle in Histogram
Trapping Rain Water
Daily Temperatures
Decode String

Frequently Asked Questions

Why record indices instead of deleting characters on the fly?

Deleting mid-scan shifts positions and makes the logic error-prone, especially with letters mixed in. Collecting bad indices into a set and doing one clean rebuild pass keeps both passes simple and linear.

How does this differ from Remove Invalid Parentheses, which returns all results?

This problem asks for any one minimal answer, which a greedy stack finds in O(n). Enumerating every distinct minimal-removal string requires BFS or backtracking with pruning, which is exponential in the worst case — a much harder problem despite the similar name.