Skip to main content

1249. Minimum Remove to Make Valid Parentheses

mediumAsked at Meta

Given a string with letters and parens, remove the minimum number of parens to make it valid. Meta asks this to test whether you can identify removals in a single stack pass (forward + backward sweeps work too).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Meta loops.

  • Glassdoor (2026-Q1)— Meta E4 onsite reports cite this as a Meta favorite string problem.
  • Blind (2025-12)— Recurring Meta interview problem; the dual-sweep solution is the expected answer.

Problem

Given a string s of '(' , ')' and lowercase English characters. Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string. Formally, a parentheses string is valid if: It is the empty string, contains only lowercase characters, or It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string.

Constraints

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

Examples

Example 1

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

Explanation: "lee(t(co)de)" and "lee(t(c)ode)" would also be accepted.

Example 2

Input
s = "a)b(c)d"
Output
"ab(c)d"

Example 3

Input
s = "))(("
Output
""

Approaches

1. Stack with index tracking (optimal)

Scan left-to-right. Push '(' indices on a stack; on ')', pop if stack non-empty, else mark this ')' for removal. At end, remaining stack entries are unmatched '(' to remove.

Time
O(n)
Space
O(n)
function minRemoveToMakeValid(s) {
  const chars = s.split('');
  const stack = [];
  for (let i = 0; i < chars.length; i++) {
    if (chars[i] === '(') stack.push(i);
    else if (chars[i] === ')') {
      if (stack.length) stack.pop();
      else chars[i] = '';
    }
  }
  while (stack.length) chars[stack.pop()] = '';
  return chars.join('');
}

Tradeoff: Single linear pass plus a stack-drain pass. Clear correctness: any ')' without a matching '(' (or vice versa) gets marked for removal.

2. Two-pass counters (alternative optimal)

Pass 1 left-to-right: remove ')' that have no matching '(' to their left. Pass 2 right-to-left: remove '(' that have no matching ')' to their right.

Time
O(n)
Space
O(n)
function minRemoveTwoPass(s) {
  // Pass 1: remove unmatched ')'
  let chars = [];
  let open = 0;
  for (const c of s) {
    if (c === '(') open++;
    else if (c === ')') {
      if (open === 0) continue;
      open--;
    }
    chars.push(c);
  }
  // Pass 2: remove unmatched '(' from the right
  const result = [];
  let close = 0;
  for (let i = chars.length - 1; i >= 0; i--) {
    if (chars[i] === ')') close++;
    else if (chars[i] === '(') {
      if (close === 0) continue;
      close--;
    }
    result.push(chars[i]);
  }
  return result.reverse().join('');
}

Tradeoff: Two passes, no explicit stack. Some interviewers prefer this because the logic mirrors the symmetry of brackets. Same complexity.

Meta-specific tips

Meta interviewers want you to articulate WHICH parens to remove: unmatched ')' have no '(' to their LEFT; unmatched '(' have no ')' to their RIGHT. The stack version captures both in one structure (stack remembers unmatched openers; mid-loop removals handle closers). The two-pass version makes the symmetry obvious.

Common mistakes

  • Trying to compute the minimum count first (the problem only asks for a valid result, not the count).
  • Modifying the string in place during the scan — confusing index management.
  • Forgetting that the string can have letters between/around parens — they must be preserved.

Follow-up questions

An interviewer at Meta may pivot to one of these next:

  • What if there were multiple bracket types (LC 921 variant)?
  • What if we needed the lexicographically smallest valid result?
  • What if we needed to return ALL valid results with minimum removals (LC 301)?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is greedy (remove first invalid char) correct?

Because each removal is locally optimal: removing an unmatched ')' on the left or an unmatched '(' on the right doesn't affect any future valid pair. The choice of WHICH unmatched char to remove doesn't change the minimum count.

Stack or two-pass — which is preferred?

Both score equally. Stack is more compact; two-pass shows symmetry. Pick whichever you can code without bugs.

Practice these live with InterviewChamp.AI

Drill Minimum Remove to Make Valid Parentheses and other Meta interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →