Remove Invalid Parentheses

Problem#

Given a string with letters, (, and ), remove the minimum number of parentheses so the result is valid. Return all unique results.

Examples#

"()())()" → ["(())()","()()()"]
"(a)())()" → ["(a())()","(a)()()"]

Constraints#

1 <= s.length <= 25.

Hints#

Hint 1

First compute the number of misplaced ( and ) to delete. Then DFS, restricting deletions to those budgets.

Approach#

Single left-to-right pass computes excess ) (r) and excess ( (l). Backtracking: at each position, optionally skip the current paren (if budget allows), or keep it. Track running open count; reject paths that go invalid. Add to result on reaching end with both budgets exhausted and balanced.

Solution#

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for (char c : s) {
            if (c == '(') ++l;
            else if (c == ')') { if (l > 0) --l; else ++r; }
        }
        set<string> out;
        function<void(int,int,int,int,string&)> dfs = [&](int i, int open, int rl, int rr, string& path) {
            if (i == (int)s.size()) {
                if (open == 0 && rl == 0 && rr == 0) out.insert(path);
                return;
            }
            char c = s[i];
            if (c == '(' && rl > 0) dfs(i + 1, open, rl - 1, rr, path);
            else if (c == ')' && rr > 0) dfs(i + 1, open, rl, rr - 1, path);
            path.push_back(c);
            if (c == '(') dfs(i + 1, open + 1, rl, rr, path);
            else if (c == ')') { if (open > 0) dfs(i + 1, open - 1, rl, rr, path); }
            else dfs(i + 1, open, rl, rr, path);
            path.pop_back();
        };
        string path;
        dfs(0, 0, l, r, path);
        return {out.begin(), out.end()};
    }
};

func removeInvalidParentheses(s string) []string {
    l, r := 0, 0
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            l++
        } else if s[i] == ')' {
            if l > 0 {
                l--
            } else {
                r++
            }
        }
    }
    out := map[string]bool{}
    path := []byte{}
    var dfs func(i, open, rl, rr int)
    dfs = func(i, open, rl, rr int) {
        if i == len(s) {
            if open == 0 && rl == 0 && rr == 0 {
                out[string(path)] = true
            }
            return
        }
        c := s[i]
        if c == '(' && rl > 0 {
            dfs(i+1, open, rl-1, rr)
        } else if c == ')' && rr > 0 {
            dfs(i+1, open, rl, rr-1)
        }
        path = append(path, c)
        if c == '(' {
            dfs(i+1, open+1, rl, rr)
        } else if c == ')' {
            if open > 0 {
                dfs(i+1, open-1, rl, rr)
            }
        } else {
            dfs(i+1, open, rl, rr)
        }
        path = path[:len(path)-1]
    }
    dfs(0, 0, l, r)
    res := make([]string, 0, len(out))
    for k := range out {
        res = append(res, k)
    }
    return res
}

from typing import List

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        l = r = 0
        for c in s:
            if c == '(':
                l += 1
            elif c == ')':
                if l > 0:
                    l -= 1
                else:
                    r += 1
        out: set[str] = set()
        path: list[str] = []

        def dfs(i: int, open_cnt: int, rl: int, rr: int) -> None:
            if i == len(s):
                if open_cnt == 0 and rl == 0 and rr == 0:
                    out.add(''.join(path))
                return
            c = s[i]
            if c == '(' and rl > 0:
                dfs(i + 1, open_cnt, rl - 1, rr)
            elif c == ')' and rr > 0:
                dfs(i + 1, open_cnt, rl, rr - 1)
            path.append(c)
            if c == '(':
                dfs(i + 1, open_cnt + 1, rl, rr)
            elif c == ')':
                if open_cnt > 0:
                    dfs(i + 1, open_cnt - 1, rl, rr)
            else:
                dfs(i + 1, open_cnt, rl, rr)
            path.pop()

        dfs(0, 0, l, r)
        return list(out)

function removeInvalidParentheses(s) {
    let l = 0, r = 0;
    for (const c of s) {
        if (c === '(') l++;
        else if (c === ')') {
            if (l > 0) l--;
            else r++;
        }
    }
    const out = new Set();
    const path = [];
    const dfs = (i, open, rl, rr) => {
        if (i === s.length) {
            if (open === 0 && rl === 0 && rr === 0) out.add(path.join(''));
            return;
        }
        const c = s[i];
        if (c === '(' && rl > 0) dfs(i + 1, open, rl - 1, rr);
        else if (c === ')' && rr > 0) dfs(i + 1, open, rl, rr - 1);
        path.push(c);
        if (c === '(') dfs(i + 1, open + 1, rl, rr);
        else if (c === ')') {
            if (open > 0) dfs(i + 1, open - 1, rl, rr);
        } else dfs(i + 1, open, rl, rr);
        path.pop();
    };
    dfs(0, 0, l, r);
    return Array.from(out);
}

class Solution {
    private Set<String> out;
    private StringBuilder path;
    private String s;

    public List<String> removeInvalidParentheses(String s) {
        this.s = s;
        int l = 0, r = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') l++;
            else if (c == ')') {
                if (l > 0) l--;
                else r++;
            }
        }
        out = new HashSet<>();
        path = new StringBuilder();
        dfs(0, 0, l, r);
        return new ArrayList<>(out);
    }

    private void dfs(int i, int open, int rl, int rr) {
        if (i == s.length()) {
            if (open == 0 && rl == 0 && rr == 0) out.add(path.toString());
            return;
        }
        char c = s.charAt(i);
        if (c == '(' && rl > 0) dfs(i + 1, open, rl - 1, rr);
        else if (c == ')' && rr > 0) dfs(i + 1, open, rl, rr - 1);
        path.append(c);
        if (c == '(') dfs(i + 1, open + 1, rl, rr);
        else if (c == ')') {
            if (open > 0) dfs(i + 1, open - 1, rl, rr);
        } else dfs(i + 1, open, rl, rr);
        path.deleteCharAt(path.length() - 1);
    }
}

function removeInvalidParentheses(s: string): string[] {
    let l = 0;
    let r = 0;
    for (const c of s) {
        if (c === '(') l++;
        else if (c === ')') {
            if (l > 0) l--;
            else r++;
        }
    }
    const out = new Set<string>();
    const path: string[] = [];
    const dfs = (i: number, open: number, rl: number, rr: number): void => {
        if (i === s.length) {
            if (open === 0 && rl === 0 && rr === 0) out.add(path.join(''));
            return;
        }
        const c = s[i];
        if (c === '(' && rl > 0) dfs(i + 1, open, rl - 1, rr);
        else if (c === ')' && rr > 0) dfs(i + 1, open, rl, rr - 1);
        path.push(c);
        if (c === '(') dfs(i + 1, open + 1, rl, rr);
        else if (c === ')') {
            if (open > 0) dfs(i + 1, open - 1, rl, rr);
        } else dfs(i + 1, open, rl, rr);
        path.pop();
    };
    dfs(0, 0, l, r);
    return Array.from(out);
}

Editorial#

Computing (l, r) budgets upfront prunes the search to only deletions consistent with the minimum count. The set deduplicates results from independent branches that produce the same string.

Complexity#

Time: O(n × 2^n) worst case.
Space: O(n).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#