LC 301. Remove Invalid Parentheses

Sarthak Sehgal · March 15, 2020

hard   strings

Solution

The idea is to keep removing a bracket in a “breadth-first” manner and checking if the string is valid. By “breadth-first”, I mean that we will first remove a bracket from all the possible positions of the given string and store the resulting strings, then again we’ll do the same for each resulting string and so on. This way, after the first iteration we have all the strings with 1 bracket remove, after the second iteration we have all the strings with 2 brackets removed and so on. Since we have to remove the minimum number of brackets, if iteration ‘i’ gives us a valid string then we can stop at that as any iteration > i will have more than i number of brackets removed. To summarise:

  1. Remove brackets in a breadth first manner using a queue
  2. For each string, check if it is valid
  3. If the string is valid, stop adding new strings to the queue
  4. If the string is not valid, continue removing bracket

Further, with a little trick, we can avoid the time consuming check for validity of a string in step 2. Note that the number of mismatched brackets are the minimum number of brackets we need to remove to make the string valid. This is also the same as minimum number of brackets which can be added to make the string valid as in LC 921. We can use the below helper function to get that count:

int countInvalid (string s) {
    int open = 0;
    int invalid = 0;
    
    for (char c : s) {
        if (!open && c==')')
            invalid++;
        else if (c=='(')
            open++;
        else if (c==')')
            open--;
    }
    
    invalid += open;
    
    return invalid;
}

Now, we can do the following to get our answer:

  1. Calculate the minimum number of mismatched brackets. This is the min number of brackets to be removed.
  2. Remove brackets in a “breadth-first” manner and store the strings in a queue. Use a set to make sure that duplicate strings are not pushed into the queue.
  3. When the number of removed brackets is equal to the count in step 1, check if the string is valid. If the string is valid, push it into the answer.
vector<string> removeInvalidParentheses(string s) {
    int invalidCount = countInvalid(s); // countInvalid function mentioned above
    vector<string> ans;

    // edge cases
    if (invalidCount == 0)
        return {s};
    if (invalidCount == s.length())
        return {""};

    queue<string> q;
    unordered_set<string> vis;
    int removed = 0;
    q.push(s);

    while (removed <= invalidCount) {
        int n = q.size();
        while (n > 0) {
            string temp = q.front();
            q.pop();
            if (removed != invalidCount) {
                // step 2
                for (int i=0; i<temp.length(); i++) {
                    if (temp[i] != ')' && temp[i] != '(')
                        continue;
                    string t = temp.substr(0, i)+temp.substr(i+1);
                    if (vis.find(t) == vis.end()) {
                        q.push(t);
                        vis.insert(t);
                    }
                }
            } else {
                // step 3
                if (countInvalid(temp) == 0)
                    ans.push_back(temp);
            }
            n--;
        }
        removed++;
    }

    return ans;
}

Twitter, Facebook