Minimum Remove to Make Valid Parentheses
Tidy up the brackets and keep every letter. s has lowercase letters, "(" and ")". Remove as few parentheses as you can so the ones left are balanced: every ")" closes an earlier "(" that is still open, and no "(" is left open at the end. Never remove a letter. Return the cleaned string. When several results remove the same number of parentheses, any one of them is accepted. Limits: 1 <= s.length <= 100000. Hint: keep the positions of the "(" that are still waiting for a ")". Examples: s = "lee(t(c)o)de)" => "lee(t(c)o)de" ("lee(t(co)de)" and "lee(t(c)ode)" are accepted too) s = "a)b(c)d" => "ab(c)d" s = "))((" => ""
A search box lets people group their words with parentheses, and one stray bracket makes the whole query fail. Before the query runs, you clean it by removing as few parentheses as possible so the ones left are balanced: every ')' closes an earlier '(' that is still open, and nothing is left open at the end. Letters are never touched, and when several results remove the same number of parentheses, any one of them is accepted. Interviewers ask it because it looks like Valid Parentheses but wants you to say which brackets are the stray ones, not just whether one exists. The classic traps are comparing only the totals of '(' and ')' without looking at their order, removing a bracket from the wrong side, and forgetting the '(' still open when the string ends. Expect up to 100,000 characters, so aim for one pass over the string rather than a fresh scan after every deletion.
Examples
You write
min_remove_to_make_valid(s: str)
Example 1
- Input
- s = "lee(t(c)o)de)"
- returns
- "lee(t(c)o)de" or "lee(t(c)ode)" or "lee(t(co)de)"
Example 2
- Input
- s = "a)b(c)d"
- returns
- "ab(c)d"
Save this for your laptop
The editor and Run need a bigger screen. The link opens Minimum Remove to Make Valid Parentheses ready to code. It is free, and the editor needs no account.
The pattern behind it
Strings
I reach for it when
- The input is text and the answer is a count, a substring or a new string.
- You need to compare, reverse or rebuild characters.
Say this before you type. Say which array pattern the string is hiding before you touch a character.
All 51 Strings problemsStack
I reach for it when
- Things must close in the reverse order they opened.
- You need the nearest earlier or later item that is bigger or smaller.
Say this before you type. Say what each item on the stack is waiting for, and what lets you pop it.
All 17 Stack problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.