Remove Invalid Parentheses

Hard
1252.

Remove Invalid Parentheses

Remove Invalid Parentheses is a hard coding problem on strings, breadth-first search and backtracking, asked in Amazon, Google, Meta and Rubrik interviews.

A string s holds lowercase letters and the brackets ( and ). It is valid when its brackets are balanced: reading left to right, no ) ever appears without an unmatched ( before it, and every ( is matched by the end. Letters are ignored.

Delete the minimum number of brackets so that the string becomes valid, and return every distinct valid string you can reach with that minimum number of deletions.

Return the strings sorted in ascending lexicographic order (by character code, so ( < ) < letters). If the only option is to delete every bracket and nothing is left, the answer is [""].

Example 1

Input
s = "(c)o)d(e)"
Output
["(c)od(e)","(co)d(e)"]
Explanation
One `)` is surplus; deleting either of the first two gives a valid string.

Example 2

Input
s = "))("
Output
[""]

Example 3

Input
s = "x(()"
Output
["x()"]
Explanation
Deleting either `(` produces the same string, which is listed once.

Constraints

  • 1 <= s.length <= 25
  • s consists of lowercase English letters and '(' and ')'
  • There are at most 20 brackets in s
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove Invalid Parentheses — Solution in Python, Java & C++

Remove Invalid Parentheses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Remove Invalid Parentheses is a hard coding problem on strings, breadth-first search and backtracking, asked in Amazon, Google, Meta and Rubrik interviews.

Problem statement

A string s holds lowercase letters and the brackets ( and ). It is valid when its brackets are balanced: reading left to right, no ) ever appears without an unmatched ( before it, and every ( is matched by the end. Letters are ignored.

Delete the minimum number of brackets so that the string becomes valid, and return every distinct valid string you can reach with that minimum number of deletions.

Return the strings sorted in ascending lexicographic order (by character code, so ( < ) < letters). If the only option is to delete every bracket and nothing is left, the answer is [""].

Example 1

Input: s = "(c)o)d(e)"
Output: ["(c)od(e)","(co)d(e)"]
Explanation: One `)` is surplus; deleting either of the first two gives a valid string.

Example 2

Input: s = "))("
Output: [""]

Example 3

Input: s = "x(()"
Output: ["x()"]
Explanation: Deleting either `(` produces the same string, which is listed once.

Constraints

  • 1 <= s.length <= 25
  • s consists of lowercase English letters and '(' and ')'
  • There are at most 20 brackets in s

Hints for Remove Invalid Parentheses

  1. Hint 1

    One left-to-right pass tells you how many ( and how many ) must be deleted: count the ) that have no partner, and the ( still open at the end.

  2. Hint 2

    Search over the string with those two budgets: at each bracket either delete it (if its budget allows) or keep it, tracking how many ( are currently open.

  3. Hint 3

    Never keep a ) when nothing is open, and accept a finished string only when both budgets are spent and nothing is open. Collect results in a set to remove duplicates, then sort.

How to solve Remove Invalid Parentheses

The minimum number of deletions is known in advance — a balance scan counts the unmatched ) and the leftover ( — so a depth-first search that spends exactly those budgets enumerates precisely the optimal strings.

Approach

  1. Scan s with a counter: ( increments it; ) decrements it if positive, otherwise increments right (an unmatched )). At the end the counter is left, the unmatched (.
  2. DFS over positions i with state (open, left, right) and the string built so far.
  3. At a letter, keep it. At (: if left > 0, branch on deleting it; also branch on keeping it (open + 1).
  4. At ): if right > 0, branch on deleting it; if open > 0, branch on keeping it (open - 1).
  5. At the end, record the built string if open == left == right == 0.
  6. Deduplicate with a set and sort the result.

Why it works

No valid string can be reached with fewer than left + right deletions: every unmatched ) found by the scan needs a ( before it that does not exist, and every leftover ( needs a later ). Conversely, the search keeps the running balance non-negative and requires it to end at zero, so every recorded string is valid, and it only records strings that used exactly the minimum budgets. Every optimal deletion set is one path of the search, so nothing is missed.

Complexity

  • Time — O(2^b · n) in the worst case for b brackets, far less in practice because the budgets prune most branches
  • Space — O(n) recursion depth plus the output

Pitfalls

  • Different deletion sets can yield the same string ("x(()" → "x()" twice) — deduplicate.
  • Deleting more than the minimum also gives valid strings; they must not be reported.
  • When the answer is to delete every bracket of a letter-free string, the result is a list holding the empty string, not an empty list.

Reference solution

Python

from typing import List

def removeInvalidParentheses(s: str) -> List[str]:
    left = right = 0
    for c in s:
        if c == "(":
            left += 1
        elif c == ")":
            if left > 0:
                left -= 1
            else:
                right += 1
    n = len(s)
    found = set()
    buf = []

    def dfs(i, opened, l, r):
        if i == n:
            if l == 0 and r == 0 and opened == 0:
                found.add("".join(buf))
            return
        c = s[i]
        if c == "(":
            if l > 0:
                dfs(i + 1, opened, l - 1, r)
            buf.append(c)
            dfs(i + 1, opened + 1, l, r)
            buf.pop()
        elif c == ")":
            if r > 0:
                dfs(i + 1, opened, l, r - 1)
            if opened > 0:
                buf.append(c)
                dfs(i + 1, opened - 1, l, r)
                buf.pop()
        else:
            buf.append(c)
            dfs(i + 1, opened, l, r)
            buf.pop()

    dfs(0, 0, left, right)
    return sorted(found)

Java

static void ripDfs(String s, int i, int opened, int l, int r, StringBuilder cur, TreeSet<String> found) {
    if (i == s.length()) {
        if (l == 0 && r == 0 && opened == 0) found.add(cur.toString());
        return;
    }
    char c = s.charAt(i);
    if (c == '(') {
        if (l > 0) ripDfs(s, i + 1, opened, l - 1, r, cur, found);
        cur.append(c);
        ripDfs(s, i + 1, opened + 1, l, r, cur, found);
        cur.setLength(cur.length() - 1);
    } else if (c == ')') {
        if (r > 0) ripDfs(s, i + 1, opened, l, r - 1, cur, found);
        if (opened > 0) {
            cur.append(c);
            ripDfs(s, i + 1, opened - 1, l, r, cur, found);
            cur.setLength(cur.length() - 1);
        }
    } else {
        cur.append(c);
        ripDfs(s, i + 1, opened, l, r, cur, found);
        cur.setLength(cur.length() - 1);
    }
}

public static String[] removeInvalidParentheses(String s) {
    int left = 0, right = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') left++;
        else if (c == ')') {
            if (left > 0) left--;
            else right++;
        }
    }
    TreeSet<String> found = new TreeSet<>();
    ripDfs(s, 0, 0, left, right, new StringBuilder(), found);
    return found.toArray(new String[0]);
}

C++

static void ripDfs(const string& s, int i, int opened, int l, int r, string& cur, set<string>& found) {
    if (i == (int)s.size()) {
        if (l == 0 && r == 0 && opened == 0) found.insert(cur);
        return;
    }
    char c = s[i];
    if (c == '(') {
        if (l > 0) ripDfs(s, i + 1, opened, l - 1, r, cur, found);
        cur.push_back(c);
        ripDfs(s, i + 1, opened + 1, l, r, cur, found);
        cur.pop_back();
    } else if (c == ')') {
        if (r > 0) ripDfs(s, i + 1, opened, l, r - 1, cur, found);
        if (opened > 0) {
            cur.push_back(c);
            ripDfs(s, i + 1, opened - 1, l, r, cur, found);
            cur.pop_back();
        }
    } else {
        cur.push_back(c);
        ripDfs(s, i + 1, opened, l, r, cur, found);
        cur.pop_back();
    }
}

vector<string> removeInvalidParentheses(string s) {
    int left = 0, right = 0;
    for (char c : s) {
        if (c == '(') left++;
        else if (c == ')') {
            if (left > 0) left--;
            else right++;
        }
    }
    set<string> found;
    string cur;
    ripDfs(s, 0, 0, left, right, cur, found);
    return vector<string>(found.begin(), found.end());
}

JavaScript

var removeInvalidParentheses = function(s) {
    var left = 0, right = 0;
    for (var i = 0; i < s.length; i++) {
        if (s[i] === "(") left++;
        else if (s[i] === ")") {
            if (left > 0) left--;
            else right++;
        }
    }
    var n = s.length;
    var found = new Set();
    var dfs = function(i, opened, l, r, cur) {
        if (i === n) {
            if (l === 0 && r === 0 && opened === 0) found.add(cur);
            return;
        }
        var c = s[i];
        if (c === "(") {
            if (l > 0) dfs(i + 1, opened, l - 1, r, cur);
            dfs(i + 1, opened + 1, l, r, cur + c);
        } else if (c === ")") {
            if (r > 0) dfs(i + 1, opened, l, r - 1, cur);
            if (opened > 0) dfs(i + 1, opened - 1, l, r, cur + c);
        } else {
            dfs(i + 1, opened, l, r, cur + c);
        }
    };
    dfs(0, 0, left, right, "");
    return Array.from(found).sort();
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Breadth-First Search (BFS)