Skip to main content
CodePeet

Minimum Remove to Make Valid Parentheses

Try it yourself
MediumProblemExternal link

Description

You get a string s of lowercase English letters and the brackets ( and ). Remove as few brackets as possible so that the ones left are valid: every ( is closed by a ) after it, and every ) closes a ( before it. Letters can sit anywhere and are never removed.

Return the string that's left. Often several strings remove the fewest brackets; any of them is accepted.

Examples

Example 1

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

Output: "lee(t(c)o)de"

Explanation: The last ')' closes nothing, so it goes. "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"

Explanation: The ')' after a closes nothing, so it goes.

Example 3

Input: s = "))(("

Output: ""

Explanation: No bracket has a partner, so all four go. An empty string is valid.

Example 4

Input: s = "a)b(c(d)"

Output: "abc(d)"

Explanation: The ')' after a closes nothing, and one '(' is never closed. "abc(d)" and "ab(cd)" both remove two brackets, the fewest, so either is accepted.

Constraints

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

Editorial

Brute Force

Intuition

Repair the string one bracket at a time. Read it from the left, counting the open (: a ) that arrives when nothing is open can never close anything, so it has to go. If no ) breaks but some ( are still open at the end, read from the right the same way: the first ( with nothing after it left to close it has to go. Remove that one bracket, check the new string from the start, and repeat until neither scan finds a break.

Every bracket removed has no partner, so no answer can remove fewer.

Step-by-Step Explanation

Let's trace s = "a)b(c(d)":

  1. From the left, the ) at index 1 arrives with nothing open. Remove it: "ab(c(d)".
  2. From the left nothing breaks, but one ( is still open at the end. From the right, the ( at index 2 has nothing after it to close it. Remove it: "abc(d)".
  3. Both scans pass, so "abc(d)" is valid, after 2 removals.

Fix One Break at a Time — The bracket that has to go is orange; each removal starts the scan over.

Algorithm

  1. Scan s from the left with a count of open (. If a ) takes the count below zero, that ) is the break.
  2. Otherwise, scan from the right with a count of ). If a ( takes it below zero, that ( is the break.
  3. If there's a break, remove it and go back to step 1. If not, return s.

Code

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        while (true) {
            int bad = firstBreak(s);
            if (bad == -1) return s;
            s.erase(s.begin() + bad);            // remove it, then check the new string from the start
        }
    }

private:
    // the position of a bracket that has to go, or -1 if s is valid
    int firstBreak(const string& s) {
        int depth = 0;
        for (int i = 0; i < (int)s.size(); i++) {         // from the left: a ')' with nothing open
            if (s[i] == '(') depth++;
            else if (s[i] == ')' && --depth < 0) return i;
        }
        depth = 0;
        for (int i = (int)s.size() - 1; i >= 0; i--) {    // from the right: a '(' with nothing to close it
            if (s[i] == ')') depth++;
            else if (s[i] == '(' && --depth < 0) return i;
        }
        return -1;
    }
};

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        while True:
            bad = self.first_break(s)
            if bad == -1:
                return s
            s = s[:bad] + s[bad + 1:]             # remove it, then check the new string from the start

    def first_break(self, s):
        """The position of a bracket that has to go, or -1 if s is valid."""
        depth = 0
        for i, c in enumerate(s):                 # from the left: a ')' with nothing open
            if c == "(":
                depth += 1
            elif c == ")":
                depth -= 1
                if depth < 0:
                    return i
        depth = 0
        for i in range(len(s) - 1, -1, -1):       # from the right: a '(' with nothing to close it
            if s[i] == ")":
                depth += 1
            elif s[i] == "(":
                depth -= 1
                if depth < 0:
                    return i
        return -1

class Solution {
    public String minRemoveToMakeValid(String s) {
        while (true) {
            int bad = firstBreak(s);
            if (bad == -1) return s;
            s = s.substring(0, bad) + s.substring(bad + 1);   // remove it, then check the new string from the start
        }
    }

    // the position of a bracket that has to go, or -1 if s is valid
    private int firstBreak(String s) {
        int depth = 0;
        for (int i = 0; i < s.length(); i++) {             // from the left: a ')' with nothing open
            char c = s.charAt(i);
            if (c == '(') depth++;
            else if (c == ')' && --depth < 0) return i;
        }
        depth = 0;
        for (int i = s.length() - 1; i >= 0; i--) {        // from the right: a '(' with nothing to close it
            char c = s.charAt(i);
            if (c == ')') depth++;
            else if (c == '(' && --depth < 0) return i;
        }
        return -1;
    }
}

var minRemoveToMakeValid = function(s) {
    while (true) {
        const bad = firstBreak(s);
        if (bad === -1) return s;
        s = s.slice(0, bad) + s.slice(bad + 1);   // remove it, then check the new string from the start
    }
};

// the position of a bracket that has to go, or -1 if s is valid
function firstBreak(s) {
    let depth = 0;
    for (let i = 0; i < s.length; i++) {          // from the left: a ')' with nothing open
        if (s[i] === "(") depth++;
        else if (s[i] === ")" && --depth < 0) return i;
    }
    depth = 0;
    for (let i = s.length - 1; i >= 0; i--) {     // from the right: a '(' with nothing to close it
        if (s[i] === ")") depth++;
        else if (s[i] === "(" && --depth < 0) return i;
    }
    return -1;
}

Complexity Analysis

Time Complexity: O(n²)

Up to n removals, each after a scan and a copy of the string.

Space Complexity: O(n)

The copy of the string.

Why This Approach Is Not Efficient

A string of 10^5 unmatched brackets needs 10^5 removals, each one a full scan and a copy: about 10^10 steps (over the time limit in Python, Java and JavaScript).

But the removals don't depend on each other. A ) with nothing open before it has no partner whatever else is removed, and neither does a ( that's never closed. So find them all in one scan: match each ) with the most recent open (, which is what a stack does, and remove whatever is left unmatched.

Better Approach - A Stack of Open Positions

Intuition

Read s left to right and push the position of each (, not the character, so you know later which bracket to remove. A ) closes the most recent open (: pop it. A ) that finds the stack empty has nothing to close, so mark it for removal at once.

A ( can only be judged at the end: every position still on the stack was never closed, so mark those too. Then build the answer from the unmarked characters.

Step-by-Step Explanation

Let's trace s = "a)b(c(d)":

  1. ) at index 1 finds the stack empty: mark it.
  2. ( at index 3: push 3. The stack holds 3.
  3. ( at index 5: push 5. The stack holds 3, 5.
  4. ) at index 7 closes the ( at 5: pop it.
  5. The end. The ( at 3 is still on the stack, never closed: mark it. Removing the marked brackets leaves "abc(d)".

Removing from a)b(c(d) — The stack holds positions. Red brackets are the ones removed.

Algorithm

  1. For each index i: if s[i] is (, push i. If it's ), pop if the stack isn't empty; otherwise mark i.
  2. Mark every index still on the stack.
  3. Return the characters of s whose index isn't marked, in order.

Code

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> open;                         // positions of the '(' still open
        vector<bool> drop(s.size(), false);      // the brackets to remove
        for (int i = 0; i < (int)s.size(); i++) {
            if (s[i] == '(') {
                open.push(i);
            } else if (s[i] == ')') {
                if (!open.empty()) open.pop();   // it closes the most recent open '('
                else drop[i] = true;             // nothing open: one ')' too many
            }
        }
        while (!open.empty()) {                  // still open at the end: one '(' too many each
            drop[open.top()] = true;
            open.pop();
        }
        string out;
        for (int i = 0; i < (int)s.size(); i++)
            if (!drop[i]) out += s[i];
        return out;
    }
};

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = []                           # positions of the '(' still open
        drop = set()                         # the brackets to remove
        for i, c in enumerate(s):
            if c == "(":
                stack.append(i)
            elif c == ")":
                if stack:
                    stack.pop()              # it closes the most recent open '('
                else:
                    drop.add(i)              # nothing open: one ')' too many
        drop.update(stack)                   # still open at the end: one '(' too many each
        return "".join(c for i, c in enumerate(s) if i not in drop)

class Solution {
    public String minRemoveToMakeValid(String s) {
        Deque<Integer> stack = new ArrayDeque<>();        // positions of the '(' still open
        boolean[] drop = new boolean[s.length()];         // the brackets to remove
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else if (c == ')') {
                if (!stack.isEmpty()) stack.pop();        // it closes the most recent open '('
                else drop[i] = true;                      // nothing open: one ')' too many
            }
        }
        for (int i : stack) drop[i] = true;               // still open at the end: one '(' too many each
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < s.length(); i++)
            if (!drop[i]) out.append(s.charAt(i));
        return out.toString();
    }
}

var minRemoveToMakeValid = function(s) {
    const stack = [];                        // positions of the '(' still open
    const drop = new Set();                  // the brackets to remove
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(") {
            stack.push(i);
        } else if (s[i] === ")") {
            if (stack.length > 0) stack.pop();   // it closes the most recent open '('
            else drop.add(i);                // nothing open: one ')' too many
        }
    }
    for (const i of stack) drop.add(i);      // still open at the end: one '(' too many each
    const out = [];
    for (let i = 0; i < s.length; i++)
        if (!drop.has(i)) out.push(s[i]);
    return out.join("");
};

Complexity Analysis

Time Complexity: O(n)

One pass to match and one to build the answer, with constant work per character.

Space Complexity: O(n)

The stack and the marks hold up to n positions, and the answer up to n characters.

Why This Approach Is Not Efficient

It's linear, but the stack stores a position for every open ( just to learn which ( are never closed. You don't need to know which; how many is enough.

Once the stray ) are gone, say depth ( are still open. Dropping the last depth of them always works. From the first dropped ( on, nothing else opens, so the depth at each point is just the number of ) still to come: never negative, and zero at the end. Two counters can do that.

Optimal Approach - Two Passes With Counters

Intuition

Pass 1 reads s left to right with two counters: depth, how many ( are open, and opened, how many ( were kept. A ) that arrives at depth 0 is dropped; everything else is kept. At the end, depth of the kept ( were never closed.

Pass 2 reads the kept text and keeps only its first keep = opened − depth (, dropping the rest. It has to be the last ones that go: dropping an early ( can strand the ) that closed it. In ()(, dropping the first ( would leave )(.

Step-by-Step Explanation

Let's trace s = "a)b(c(d)":

  1. ) at index 1: nothing is open, so drop it.
  2. ( at index 3: keep it; opened is 1, depth 1.
  3. ( at index 5: keep it; opened is 2, depth 2.
  4. ) at index 7: it closes one; depth is 1.
  5. Pass 1 kept "ab(c(d)". depth is 1: that many ( are never closed, so keep only the first opened − depth = 1.
  6. ( at index 2 of the kept text is the first (: keep it.
  7. ( at index 4 of the kept text comes after the first (: drop it.
  8. The answer is "ab(cd)".

The stack answered "abc(d)" and this answers "ab(cd)". Both remove two brackets and both are valid, so both are accepted.

Count, Then Drop the Last Open Brackets — The top row is read, the bottom row is built; dropped brackets are orange.

Algorithm

  1. Pass 1: for each character, if it's (, keep it and add 1 to opened and depth. If it's ) and depth is 0, drop it; otherwise keep it and subtract 1 from depth. Keep every letter.
  2. Set keep = opened − depth.
  3. Pass 2: for each kept character, drop a ( once keep is 0; otherwise keep it, and if it's (, subtract 1 from keep.
  4. Return what pass 2 kept.

Code

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        string kept;                             // pass 1: s without the ')' that close nothing
        int opened = 0, depth = 0;               // '(' kept so far, and how many are still open
        for (char c : s) {
            if (c == '(') {
                opened++;
                depth++;
            } else if (c == ')') {
                if (depth == 0) continue;        // nothing open: drop it
                depth--;
            }
            kept += c;
        }
        int keep = opened - depth;               // depth '(' never closed: keep only the first ones
        string out;
        for (char c : kept) {                    // pass 2: drop every '(' after the first keep
            if (c == '(') {
                if (keep == 0) continue;
                keep--;
            }
            out += c;
        }
        return out;
    }
};

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        kept = []                                 # pass 1: s without the ')' that close nothing
        opened = depth = 0                        # '(' kept so far, and how many are still open
        for c in s:
            if c == "(":
                opened += 1
                depth += 1
            elif c == ")":
                if depth == 0:
                    continue                      # nothing open: drop it
                depth -= 1
            kept.append(c)
        keep = opened - depth                     # depth '(' never closed: keep only the first ones
        out = []
        for c in kept:                            # pass 2: drop every '(' after the first keep
            if c == "(":
                if keep == 0:
                    continue
                keep -= 1
            out.append(c)
        return "".join(out)

class Solution {
    public String minRemoveToMakeValid(String s) {
        StringBuilder kept = new StringBuilder();         // pass 1: s without the ')' that close nothing
        int opened = 0, depth = 0;                        // '(' kept so far, and how many are still open
        for (char c : s.toCharArray()) {
            if (c == '(') {
                opened++;
                depth++;
            } else if (c == ')') {
                if (depth == 0) continue;                 // nothing open: drop it
                depth--;
            }
            kept.append(c);
        }
        int keep = opened - depth;                        // depth '(' never closed: keep only the first ones
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < kept.length(); i++) {        // pass 2: drop every '(' after the first keep
            char c = kept.charAt(i);
            if (c == '(') {
                if (keep == 0) continue;
                keep--;
            }
            out.append(c);
        }
        return out.toString();
    }
}

var minRemoveToMakeValid = function(s) {
    const kept = [];                         // pass 1: s without the ')' that close nothing
    let opened = 0, depth = 0;               // '(' kept so far, and how many are still open
    for (const c of s) {
        if (c === "(") {
            opened++;
            depth++;
        } else if (c === ")") {
            if (depth === 0) continue;       // nothing open: drop it
            depth--;
        }
        kept.push(c);
    }
    let keep = opened - depth;               // depth '(' never closed: keep only the first ones
    const out = [];
    for (const c of kept) {                  // pass 2: drop every '(' after the first keep
        if (c === "(") {
            if (keep === 0) continue;
            keep--;
        }
        out.push(c);
    }
    return out.join("");
};

Complexity Analysis

Time Complexity: O(n)

Two passes, with constant work per character.

Space Complexity: O(n)

The text pass 1 keeps, and the answer. The bookkeeping is two counters, where the stack version kept up to n positions.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Leaving the unclosed ( in. return "".join(c for i, c in enumerate(s) if i not in drop)

On s = "a(b" it returns "a(b", which isn't valid; the answer is "ab". A ) with nothing open is caught as it's read, but a ( can only be judged at the end. Whatever is still on the stack then was never closed, and has to go too.

Balancing the counts, not the order. extra = s.count(")") - s.count("(")

On s = ")(" it returns ")(", which isn't valid; the answer is "". Equal numbers of ( and ) don't make a string valid: in )( the ) comes before anything it could close. Which bracket closes which depends on the order, and only a scan in order sees it.

Dropping the extra ( from the left. if c == "(" and open_ > 0:

On s = "()(" it returns ")(", which isn't valid; the answer is "()". After the first pass, the number of ( to remove is right, but which ones matters. Dropping an early ( can strand the ) that closed it. Dropping the last ones never does: from the first dropped ( on, nothing else opens, so every ) after it still has an earlier ( to close.

Where This Pattern Is Taught

This problem practises matching brackets with a stack, keeping positions so you know what to remove. It's taught in Matching Brackets with a Stack, along with Valid Parentheses and why the stack's removals are the fewest.