Minimum Remove to Make Valid Parentheses

MediumStackstack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a string s of lowercase letters, '(' and ')'. Delete the **minimum** number of parentheses so the remaining string is balanced: every ')' closes an earlier unmatched '(', and every '(' is eventually closed. Letters are never deleted. Several minimal deletions can exist, so the output is pinned to one: scanning left to right, pair each ')' with the **nearest earlier '(' that is still unpaired**; a ')' with no such '(' is deleted, and every '(' that is still unpaired at the end is deleted. This removes the fewest characters. Return the resulting string (possibly empty).

Examples

Input: s = "a)b(c)d"
Output: "ab(c)d"
The first ')' has no '(' before it, so it is deleted.
Input: s = "(a(b)"
Output: "a(b)"
The ')' pairs with the nearer '(' at index 2, so the '(' at index 0 stays unpaired and is deleted.
Input: s = "))(("
Output: ""
No parenthesis can be paired, so all four are deleted.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More stack problems