301. Remove Invalid Parentheses

String Backtracking Breadth-First Search

Problem Overview

Removing the fewest parentheses means fixing exactly the places where the string goes wrong.

Intuition

Removing the fewest parentheses means fixing exactly the places where the string goes wrong. Scanning left to right, the first time closers outnumber openers, one closer at or before that point has to go, and any of them works. After that prefix is fixed, the scan continues from the same spot. Extra openers are the mirror problem, so reversing the string and swapping the roles of the two parentheses handles them with the same code. Every string that survives both passes is valid, and careful choices keep each one from being built twice.

Algorithm

1Scan from the last scan position with a balance that rises on an opener and falls on a closer.
2At the first point where the balance is negative, try removing each closer from the last removal position up to that point. Skip a closer that directly follows another closer, because removing either one gives the same string.
3Recurse on each shorter string, continuing the scan at the same index and the removals at the removed index.
4When a forward scan finishes balanced, reverse the string and run the same process with the opening parenthesis as the closer.
5When the reversed pass also finishes, reverse back and add the string to the answer.

Example Walkthrough

Input: s = "()())()"

1.The balance first goes negative at index 4, so one of the closers at indexes 1, 3, or 4 must go.
2.Removing index 1 gives "(())()". Removing index 3 gives "()()()". Index 4 directly follows another closer, so it is skipped.
3.Both strings have no extra openers, so the reversed pass changes nothing.

Output: ["(())()","()()()"]

Common Pitfalls

•Removals must not move back before the last removal point, or the same string is reached in two different orders.
•Letters are kept and never removed. Only the two parenthesis characters affect the balance.
•Trying every deletion and filtering with a set at the end works but builds far more strings.
•The answer can contain many strings, so the worst case is still exponential. The pruning only removes wasted work.

301.cs

// Approach: Scan left to right with a balance. At the first prefix where
// closers outnumber openers, one closer at or before that point must go.
// Try each closer from the last removal position onward, skipping repeats
// in a run so the same string is not built twice, then resume the scan from
// the same index. Once the forward pass is balanced, reverse the string and
// run the same pass with the roles of '(' and ')' swapped to drop extra
// openers. Every string reaching the end is valid and unique, so no final
// check or set is needed.
// Time: O(2^n * n) worst case Space: O(n) recursion beyond the output

public class Solution
{
    public IList<string> RemoveInvalidParentheses(string s)
    {
        var ans = new List<string>();
        Remove(s, 0, 0, '(', ')', ans);
        return ans;
    }

    private static void Remove(string s, int scanFrom, int removeFrom, char open, char close, List<string> ans)
    {
        int balance = 0;
        for (int i = scanFrom; i < s.Length; i++)
        {
            if (s[i] == open)
                balance++;
            else if (s[i] == close)
                balance--;
            if (balance >= 0)
                continue;

            for (int j = removeFrom; j <= i; j++)
            {
                if (s[j] == close && (j == removeFrom || s[j - 1] != close))
                    Remove(s.Remove(j, 1), i, j, open, close, ans);
            }
            return;
        }

        char[] rev = s.ToCharArray();
        Array.Reverse(rev);
        string reversed = new string(rev);
        if (open == '(')
            Remove(reversed, 0, 0, ')', '(', ans);
        else
            ans.Add(reversed);
    }
}

Was this solution helpful?