301. Remove Invalid Parentheses

2026, Oct 06 2 mins read

1. Description

Given a string s containing letters and parentheses, delete as few parentheses as possible so that the remaining parentheses are balanced. Keep every letter in its original relative order.
Return all distinct strings obtainable with this minimum number of deletions. The results can appear in any order.

2. Example

Example 1

Input: s = “()())()”
Output: ["(())()","()()()"]

Example 2

Input: s = “(a)())()”
Output: ["(a())()","(a)()()"]

Example 3

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

3. Constraints

1 <= s.length <= 25
Each character is a lowercase English letter, ‘(’ or ‘)’.
s contains no more than 20 parentheses.

4. Solutions

Backtracking

n = str.size(), p = number of parentheses, k = number of distinct answers
Time complexity: O(n * $2^p$), assuming average-case hash table operations
Space complexity: O(n + n * k), excluding the returned vector but including the deduplication set

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public:
    vector<string> removeInvalidParentheses(const string &str) {
        results.clear();
        int left_count = 0, right_count = 0;
        for (char c : str) {
            if (c == '(') {
                ++left_count;
            } else if (c == ')') {
                if (left_count > 0) {
                    --left_count;
                } else {
                    ++right_count;
                }
            }
        }

        string result;
        find_parentheses(str, 0, left_count, right_count, 0, result);
        return vector<string>(results.begin(), results.end());
    }

private:
    unordered_set<string> results;

    void find_parentheses(
        const string &str,
        int index,
        int left,
        int right,
        int balance,
        string &result) {
        if (str.size() - index < left + right || balance < 0) {
            return;
        }

        if (index == str.size()) {
            if (left == 0 && right == 0 && balance == 0) {
                results.insert(result);
            }
        } else {
            char c = str[index];
            if (c == '(') {
                if (left > 0) {
                    find_parentheses(str, index + 1, left - 1, right, balance, result);
                }

                result.push_back(c);
                find_parentheses(str, index + 1, left, right, balance + 1, result);
                result.pop_back();
            } else if (c == ')') {
                if (right > 0) {
                    find_parentheses(str, index + 1, left, right - 1, balance, result);
                }

                result.push_back(c);
                find_parentheses(str, index + 1, left, right, balance - 1, result);
                result.pop_back();
            } else {
                result.push_back(c);
                find_parentheses(str, index + 1, left, right, balance, result);
                result.pop_back();
            }
        }
    }
};

Search

Tags