Not short but kinda cool JavaScript solution


  • 0
    var removeInvalidParentheses = function(s) {
        const res = new Set();
        const maxLen = { val: -Infinity };
        helper(res, s, maxLen);
        return [...res].filter(a => a.length === maxLen.val);
    };
    
    function helper(res, s, maxLen) {
        if (res.has(s) || s.length < maxLen.val) return;
    
        // Find the minimum prefix sum with '(' worth +1 and ')' worth -1
        let sum = 0;
        let min = null;
        let minIndex = null;
        for (let i = 0; i < s.length; i++) {
            if (s[i] === '(') sum++;
            else if (s[i] === ')') sum--;
            else continue;
            if (minIndex === null || sum < min) {
                min = sum;
                minIndex = i;
            }
        }
    
        // The parentheses are valid
        if (min >= 0 && sum === 0) {
            maxLen.val = Math.max(maxLen.val, s.length);
            res.add(s);
            return;
        }
    
        let paren = '(';
        let endIndex = s.length - 1;  // too many opening parentheses before here...
        let deleteCount = sum;
        if (min < 0) {
            paren = ')';
            endIndex = minIndex;      // ...or too many closing parentheses before here
            deleteCount = -min;
        }
    
        // The positions of parentheses we can remove
        const parenPositions = [];
        for (let i = 0; i <= endIndex; i++) {
            if (s[i] === paren) parenPositions.push(i);
        }
    
        // One k-combination of parenPositions
        const deleteCombo = new Array(deleteCount).fill(0).map((a, i) => i);
        const combos = nChooseK(parenPositions.length, deleteCount);
        const attempted = new Set();
    
        // Walk through each possible removal combination
        for (let i = 0; i < combos; i++) {
            let str = '';
            for (let j = 0; j <= deleteCombo.length; j++) {
                let from = j ? parenPositions[deleteCombo[j - 1]] + 1 : 0;
                let to = j === deleteCombo.length ? s.length : parenPositions[deleteCombo[j]];
                str += s.substring(from, to);
            }
            if (!attempted.has(str)) helper(res, str, maxLen);
            attempted.add(str);
            nextCombo(deleteCombo, parenPositions.length);
        }
    }
    
    function nChooseK(n, k) {
        if (k === n || k === 0) return 1;
        if (k === 1) return n;
        if (k < n / 2) return nChooseK(n, n - k);
        let num = 1;
        for (let i = k + 1; i <= n; i++) {
            num *= i;
        }
        return num / factorial(n - k);
    }
    
    function factorial(n) {
        let res = 1;
        for (let i = 2; i <= n; i++) res *= i;
        return res;
    }
    
    // Modifies fromCombo to the next lexical k-combination (k = fromCombo.length) of a set size n
    // e.g. [0, 1, 2] => [0, 1, 3]; [1, 2, 5] => [1, 3, 4]
    function nextCombo(fromCombo, n) {
        for (let i = n - 1; i >= 0; i--) {
            if (fromCombo[i] < n - fromCombo.length + i) {
                fromCombo[i]++;
                for (let j = i + 1; j < fromCombo.length; j++) {
                    fromCombo[j] = fromCombo[j - 1] + 1;
                }
                return;
            }
        }
    }
    

    The general idea is that we can't have any negative prefix sums or a non-zero final sum. For example, s = '()())))((()' has prefix sums [1,0,1,0,-1,-2,-3,-2,-1,0,-1], so we know that we have to remove 3 closing parentheses before index endIndex = 6 (inclusive).

    After one such removal combination, s becomes '(())((()' which has prefix sums [1,2,1,0,1,2,3,2]. Since we need the last prefix sum to be 0, we know that we need to remove 2 opening parentheses after index 5 (inclusive), the first index after which every prefix sum is at least the final sum. (For simplicity the above code starts from the beginning and discards all bad combinations, which end up being combinations which do not satisfy the minimum removal stipulation.)

    Our final result for this set of removals has prefix sums [1,2,1,0,1,0] corresponding to the valid parentheses '(())()'.

    This code is decently fast (beats ~60%), but some possible optimizations are:

    • For removal of opening parentheses we could start at some startIndex which is the first index after which every prefix sum is at least the final sum.
    • We could find a better way to check attempted combinations that doesn't involve concatenating along all of s.
    • We could precompute k-combinations for reasonably small C(n, k), though this adds complexity and space.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.