Skip to content

301. Remove Invalid Parentheses

DifficultyHard

Description

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

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

Solutions

Solution 1

Thinking

We must delete as few parentheses as possible and list every optimal string. Choosing delete-or-keep at each parenthesis branches too widely, and most paths are not minimal.

A scan first yields lower bounds \(l\) and \(r\) on deletions. The search tracks remaining quotas and the current left/right counts; prune when leftover characters cannot finish the deletions or a prefix has more right parentheses than left. Try deleting (if quota remains) then keeping, and deduplicate with a set. Only paths that delete exactly the minimum survive.

 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
class Solution:
    def removeInvalidParentheses(self, s: str) -> list[str]:
        def dfs(i, l, r, lcnt, rcnt, t):
            if i == n:
                if l == 0 and r == 0:
                    ans.add(t)
                return
            if n - i < l + r or lcnt < rcnt:
                return
            if s[i] == '(' and l:
                dfs(i + 1, l - 1, r, lcnt, rcnt, t)
            elif s[i] == ')' and r:
                dfs(i + 1, l, r - 1, lcnt, rcnt, t)
            dfs(i + 1, l, r, lcnt + (s[i] == '('), rcnt + (s[i] == ')'), t + s[i])

        l = r = 0
        for c in s:
            if c == '(':
                l += 1
            elif c == ')':
                if l:
                    l -= 1
                else:
                    r += 1
        ans = set()
        n = len(s)
        dfs(0, l, r, 0, 0, '')
        return list(ans)

 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
class Solution {
    private String s;
    private int n;
    private Set<String> ans = new HashSet<>();

    public List<String> removeInvalidParentheses(String s) {
        this.s = s;
        this.n = s.length();
        int l = 0, r = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                ++l;
            } else if (c == ')') {
                if (l > 0) {
                    --l;
                } else {
                    ++r;
                }
            }
        }
        dfs(0, l, r, 0, 0, "");
        return new ArrayList<>(ans);
    }

    private void dfs(int i, int l, int r, int lcnt, int rcnt, String t) {
        if (i == n) {
            if (l == 0 && r == 0) {
                ans.add(t);
            }
            return;
        }
        if (n - i < l + r || lcnt < rcnt) {
            return;
        }
        char c = s.charAt(i);
        if (c == '(' && l > 0) {
            dfs(i + 1, l - 1, r, lcnt, rcnt, t);
        }
        if (c == ')' && r > 0) {
            dfs(i + 1, l, r - 1, lcnt, rcnt, t);
        }
        int x = c == '(' ? 1 : 0;
        int y = c == ')' ? 1 : 0;
        dfs(i + 1, l, r, lcnt + x, rcnt + y, t + c);
    }
}

 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
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        unordered_set<string> ans;
        int l = 0, r = 0, n = s.size();
        for (char& c : s) {
            if (c == '(') {
                ++l;
            } else if (c == ')') {
                if (l) {
                    --l;
                } else {
                    ++r;
                }
            }
        }
        function<void(int, int, int, int, int, string)> dfs;
        dfs = [&](int i, int l, int r, int lcnt, int rcnt, string t) {
            if (i == n) {
                if (l == 0 && r == 0) {
                    ans.insert(t);
                }
                return;
            }
            if (n - i < l + r || lcnt < rcnt) {
                return;
            }
            if (s[i] == '(' && l) {
                dfs(i + 1, l - 1, r, lcnt, rcnt, t);
            }
            if (s[i] == ')' && r) {
                dfs(i + 1, l, r - 1, lcnt, rcnt, t);
            }
            int x = s[i] == '(' ? 1 : 0;
            int y = s[i] == ')' ? 1 : 0;
            dfs(i + 1, l, r, lcnt + x, rcnt + y, t + s[i]);
        };

        dfs(0, l, r, 0, 0, "");
        return vector<string>(ans.begin(), ans.end());
    }
};

 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
func removeInvalidParentheses(s string) []string {
    vis := map[string]bool{}
    l, r, n := 0, 0, len(s)
    for _, c := range s {
        if c == '(' {
            l++
        } else if c == ')' {
            if l > 0 {
                l--
            } else {
                r++
            }
        }
    }
    var dfs func(i, l, r, lcnt, rcnt int, t string)
    dfs = func(i, l, r, lcnt, rcnt int, t string) {
        if i == n {
            if l == 0 && r == 0 {
                vis[t] = true
            }
            return
        }
        if n-i < l+r || lcnt < rcnt {
            return
        }
        if s[i] == '(' && l > 0 {
            dfs(i+1, l-1, r, lcnt, rcnt, t)
        }
        if s[i] == ')' && r > 0 {
            dfs(i+1, l, r-1, lcnt, rcnt, t)
        }
        x, y := 0, 0
        if s[i] == '(' {
            x = 1
        } else if s[i] == ')' {
            y = 1
        }
        dfs(i+1, l, r, lcnt+x, rcnt+y, t+string(s[i]))
    }
    dfs(0, l, r, 0, 0, "")
    ans := make([]string, 0, len(vis))
    for v := range vis {
        ans = append(ans, v)
    }
    return ans
}

 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
function removeInvalidParentheses(s: string): string[] {
    const n = s.length;
    let l = 0,
        r = 0;
    for (const c of s) {
        if (c === '(') {
            l++;
        } else if (c === ')') {
            if (l > 0) {
                l--;
            } else {
                r++;
            }
        }
    }

    const ans = new Set<string>();

    const dfs = (i: number, l: number, r: number, lcnt: number, rcnt: number, t: string): void => {
        if (i === n) {
            if (l === 0 && r === 0) {
                ans.add(t);
            }
            return;
        }
        if (n - i < l + r || lcnt < rcnt) {
            return;
        }
        const c = s[i];
        if (c === '(' && l > 0) {
            dfs(i + 1, l - 1, r, lcnt, rcnt, t);
        }
        if (c === ')' && r > 0) {
            dfs(i + 1, l, r - 1, lcnt, rcnt, t);
        }
        const x = c === '(' ? 1 : 0;
        const y = c === ')' ? 1 : 0;
        dfs(i + 1, l, r, lcnt + x, rcnt + y, t + c);
    };

    dfs(0, l, r, 0, 0, '');
    return Array.from(ans);
}

 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
use std::collections::HashSet;

impl Solution {
    pub fn remove_invalid_parentheses(s: String) -> Vec<String> {
        let s = s.into_bytes();
        let mut l = 0;
        let mut r = 0;
        for &c in &s {
            if c == b'(' {
                l += 1;
            } else if c == b')' {
                if l > 0 {
                    l -= 1;
                } else {
                    r += 1;
                }
            }
        }
        let mut ans = HashSet::new();

        fn dfs(
            s: &[u8],
            i: usize,
            l: usize,
            r: usize,
            lcnt: usize,
            rcnt: usize,
            t: &mut Vec<u8>,
            ans: &mut HashSet<String>,
        ) {
            let n = s.len();
            if i == n {
                if l == 0 && r == 0 {
                    ans.insert(String::from_utf8(t.clone()).unwrap());
                }
                return;
            }
            if n - i < l + r || lcnt < rcnt {
                return;
            }
            let c = s[i];
            if c == b'(' && l > 0 {
                dfs(s, i + 1, l - 1, r, lcnt, rcnt, t, ans);
            }
            if c == b')' && r > 0 {
                dfs(s, i + 1, l, r - 1, lcnt, rcnt, t, ans);
            }
            let x = if c == b'(' { 1 } else { 0 };
            let y = if c == b')' { 1 } else { 0 };
            t.push(c);
            dfs(s, i + 1, l, r, lcnt + x, rcnt + y, t, ans);
            t.pop();
        }

        dfs(&s, 0, l, r, 0, 0, &mut Vec::new(), &mut ans);
        ans.into_iter().collect()
    }
}

Comments