Remove Invalid Parentheses

Problem

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

Return all the possible results. 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.

Solution

/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function(s) {
    let res = [];
    const backtrack = (s, start, path, numOpen, numClose) => {
        if (numOpen === numClose) { // open matches close (ie. valid parentheses)
            const len = res[0]?.length ?? 0;
            if (path.length === len) {
                res.push(path);
            } else if (path.length > len) {
                res = [path];
            }
        }

        for (let i = start; i < s.length; i++) {
            if (i > start && s[i] === s[i - 1]) { // skip duplicate
                continue;
            }

            if (s[i] === ")" && numClose === numOpen) { // can't have close without matching open
                continue;
            }

            if (s[i] === ")") {
                backtrack(s, i + 1, path + s[i], numOpen, numClose + 1);
            } else if (s[i] === "(") {
                backtrack(s, i + 1, path + s[i], numOpen + 1, numClose);
            } else {
                backtrack(s, i + 1, path + s[i], numOpen, numClose);
            }
        }
    };
    backtrack(s, 0, "", 0, 0);
    return res;
};

We will implement a backtracking (DFS) solution. In our backtrack method, we keep track of where we are in s (ie. start), the path path taken so far, as well as how many opening brackets numOpen and closing brackets numClose there are in path.

When numOpen == numClose, we know path must be valid, and so we check if path has greater length compared to what we have in res (ie. does path less parentheses removed) and update res accordingly.

Next, we iterate through each value s[i] from s[start:s.length], and decide if we want to use s[i] in our path. There are two cases where we don't want to include s[i]:

• If consecutive brackets are the same, we only use the first and skip the rest to avoid duplicates in res.
• If numOpen == numClose, we can't add another closing bracket to path, as that would make it invalid.

If we do include s[i], there are three possible values that s[i] can take, either s[i] is:

• An open bracket, in which case we increment numOpen.
• A close bracket, in which case we increment numClose.
• A letter, in which case we don't mutate numOpen nor numClose.

Note that in all three cases, we update start and path the same way.