Minimum Remove to Make Valid Parentheses
Solve this Problems containing lowercase letters and parentheses, remove the minimum number of parentheses so that what remains is valid — every '(' has a matching ')' after it, and every ')' has a matching '(' before it. Any one valid result is accepted.
Repeatedly rescanning for the next offending bracket (from the left, then from the right) works, but restarts from scratch after every single removal. A single left-to-right pass with a stack of unmatched-'(' indices resolves everything without a single rescan: a ')' either matches something already open (pop it) or clearly has nothing to match (mark it for removal, immediately — no future character can ever change that). Whatever '(' indices are still on the stack once the string ends were never matched either, so those get marked too. One pass decides the fate of every character, since bracket matching only ever depends on what came before, never on what comes after.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ s.length ≤ 15 - ◆
s consists of lowercase English letters and the characters '(' and ')' - ◆
Any valid resulting string is accepted — there may be more than one
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Repeated Two-Directional Rescans
BruteFirst, repeatedly scan left to right tracking a running balance: the first ')' encountered while the balance is already 0 has no match, so remove it and restart the scan from the beginning. Repeat until a full left-to-right scan finds no such offender. Then do the mirror image: repeatedly scan right to left tracking a balance of ')' seen so far, removing the first unmatched '(' and restarting, until a full right-to-left scan is clean too. Each individual removal can trigger a fresh O(n) rescan, and there can be up to O(n) removals, giving O(n²) overall.
O(n²)O(n)1class Solution {
2 public String minRemoveToValid(String s) {
3 StringBuilder sb = new StringBuilder(s);
4 boolean changed = true;
5 while (changed) {
6 changed = false;
7 int balance = 0;
8 for (int i = 0; i < sb.length(); i++) {
9 char c = sb.charAt(i);
10 if (c == '(') {
11 balance++;
12 } else if (c == ')') {
13 if (balance == 0) {
14 sb.deleteCharAt(i);
15 changed = true;
16 break;
17 }
18 balance--;
19 }
20 }
21 }
22 changed = true;
23 while (changed) {
24 changed = false;
25 int balance = 0;
26 for (int i = sb.length() - 1; i >= 0; i--) {
27 char c = sb.charAt(i);
28 if (c == ')') {
29 balance++;
30 } else if (c == '(') {
31 if (balance == 0) {
32 sb.deleteCharAt(i);
33 changed = true;
34 break;
35 }
36 balance--;
37 }
38 }
39 }
40 return sb.toString();
41 }
42}Optimal — Single-Pass Stack of Unmatched Open-Parenthesis Indices
OptimalWalk the string once, left to right. Push the index of every '(' seen. When a ')' arrives, it immediately has a valid match if the stack isn't empty (pop the most recent unmatched '(' — they're now paired); if the stack is empty, this ')' has nothing to match and is marked for removal right away. After the pass, whatever indices remain on the stack are '(' that were never matched — mark those for removal too. Finally, rebuild the string skipping every marked index. Every character is examined once and every stack operation happens at most once per character, so this is O(n) total — no rescans needed, since a single left-to-right pass naturally handles both directions of imbalance at once.
O(n)O(n)1class Solution {
2 public String minRemoveToValid(String s) {
3 Deque<Integer> stack = new ArrayDeque<>();
4 Set<Integer> remove = new HashSet<>();
5 for (int i = 0; i < s.length(); i++) {
6 char c = s.charAt(i);
7 if (c == '(') {
8 stack.push(i);
9 } else if (c == ')') {
10 if (!stack.isEmpty()) {
11 stack.pop();
12 } else {
13 remove.add(i);
14 }
15 }
16 }
17 while (!stack.isEmpty()) {
18 remove.add(stack.pop());
19 }
20 StringBuilder sb = new StringBuilder();
21 for (int i = 0; i < s.length(); i++) {
22 if (!remove.contains(i)) sb.append(s.charAt(i));
23 }
24 return sb.toString();
25 }
26}