Remove Invalid Parentheses

Erase as few brackets as possible so every opening bracket has a matching closing bracket, and list every way to do it.

Simple way: time O(n * 2^n)
room O(n)
Clever way: time O(n * C(n, r))
room O(n)

The problem, simply

You get a string of brackets ( and ), maybe mixed with letters. It is valid when every ( has a matching ) after it, and no ) comes before its partner.

Remove the smallest possible number of brackets to make it valid. Give back every different valid string you can get with that smallest number of removals. Letters are never removed.

A story to remember it

Picture it

tree

arrayinput

In ()()) the last ) finds nobody waiting, so exactly one ) must go. Removing the one at index 1 or the one at index 3 gives two different answers.

looking now
checking
answer
rejected

Examples

One extra closing bracket

In: s = '()())()'
Out: [(())(), ()()()]

One ) has no partner. Removing different ) brackets gives two different strings.

Letters stay

In: s = '(a)())()'
Out: [(a())(), (a)()()]

Same idea. The letter a is never touched.

Backwards brackets

In: s = ')('
Out: ['']

Both must go. The empty string is valid.

Already valid

In: s = '(())'
Out: [(())]

Nothing to remove.

Only letters left over

In: s = 'x('
Out: [x]

The ( never gets closed, so it goes.

Way 1: the simple way

Try every way to keep or drop each bracket. Among the valid strings, keep only the longest ones, because longest means fewest removals.

Walk the string. For each bracket, branch twice: drop it, or keep it. Letters are always kept.
At the end, check if the string is valid by counting: +1 for (, -1 for ), never below 0, and 0 at the end.
If it is longer than the best so far, start a new answer set. If it ties, add it.

java

import java.util.*;

class Solution {
    private int best;

    public List<String> removeInvalidParentheses(String s) {
        Set<String> result = new HashSet<>();
        best = -1;
        tryAll(s, 0, new StringBuilder(), result);
        return new ArrayList<>(result);
    }

    private void tryAll(String s, int i, StringBuilder cur, Set<String> result) {
        if (i == s.length()) {
            if (!isValid(cur)) return;
            if (cur.length() > best) { best = cur.length(); result.clear(); }
            if (cur.length() == best) result.add(cur.toString());
            return;
        }
        char c = s.charAt(i);
        if (c == '(' || c == ')') tryAll(s, i + 1, cur, result);   // drop it
        cur.append(c);                                            // keep it
        tryAll(s, i + 1, cur, result);
        cur.deleteCharAt(cur.length() - 1);
    }

    private boolean isValid(CharSequence t) {
        int open = 0;
        for (int k = 0; k < t.length(); k++) {
            char c = t.charAt(k);
            if (c == '(') open++;
            else if (c == ')' && --open < 0) return false;
        }
        return open == 0;
    }
}

How long it takes: 2^n strings for n brackets, each checked in O(n), so O(n * 2^n). Extra room: the current string and the call stack, O(n), besides the answers.

Way 2: the clever way

Count first, then search with a budget.

Walk once with a counter. A ( adds a waiting hand. A ) uses one if there is one, otherwise it is a ) that must go. At the end, the waiting hands are ( that must go. Call these openRem and closeRem.
Walk the string again, deciding remove or keep for each character:
- Remove a ( only if openRem > 0, and a ) only if closeRem > 0.
- Keep a ) only if some ( kept so far is still waiting. Otherwise that branch can never become valid.
At the end, if both budgets are 0 and nothing is waiting, the string is an answer. A set removes repeats.

Keep or remove each bracket, with the removal count as a budget

01 / 14

tree

arrayinput

Count first: we must remove 0 '(' and 1 ')'. Then walk the letters and decide keep or remove for each.

remove (: 0
remove ): 1
open: 0

looking now
checking
seen
done
answer
rejected
path

java

import java.util.*;

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        int openRem = 0, closeRem = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') openRem++;
            else if (c == ')') {
                if (openRem > 0) openRem--;      // matches an earlier (
                else closeRem++;                 // nobody to match: this kind must go
            }
        }
        Set<String> result = new HashSet<>();
        build(s, 0, 0, openRem, closeRem, new StringBuilder(), result);
        return new ArrayList<>(result);
    }

    // waiting = kept ( minus kept ) so far
    private void build(String s, int i, int waiting, int openRem, int closeRem,
                       StringBuilder cur, Set<String> result) {
        if (i == s.length()) {
            if (waiting == 0 && openRem == 0 && closeRem == 0) result.add(cur.toString());
            return;
        }
        char c = s.charAt(i);
        if (c == '(' && openRem > 0) build(s, i + 1, waiting, openRem - 1, closeRem, cur, result);
        if (c == ')' && closeRem > 0) build(s, i + 1, waiting, openRem, closeRem - 1, cur, result);

        int len = cur.length();
        cur.append(c);                                       // keep it
        if (c == '(') build(s, i + 1, waiting + 1, openRem, closeRem, cur, result);
        else if (c == ')') {
            if (waiting > 0) build(s, i + 1, waiting - 1, openRem, closeRem, cur, result);
        } else build(s, i + 1, waiting, openRem, closeRem, cur, result);
        cur.setLength(len);                                  // undo
    }
}

How long it takes: with r removals to make, at most C(n, r) ways exist to choose them, and each costs O(n). So O(n * C(n, r)), which is far smaller than 2^n when r is small. Extra room: O(n) for the string and the call stack, besides the answers.

Another way: breadth first search

Think of each string as a spot on a map. One step removes one bracket. Search in rings: first the input itself, then every string with one bracket removed, then two, and so on. The first ring that holds any valid string is the answer, because it uses the fewest removals.

java

import java.util.*;

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList<>();
        Set<String> seen = new HashSet<>();
        Queue<String> line = new ArrayDeque<>();
        line.add(s);
        seen.add(s);
        boolean found = false;
        while (!line.isEmpty()) {
            String cur = line.poll();
            if (isValid(cur)) {
                result.add(cur);
                found = true;
            }
            if (found) continue;                  // do not go one ring deeper
            for (int i = 0; i < cur.length(); i++) {
                char c = cur.charAt(i);
                if (c != '(' && c != ')') continue;
                String next = cur.substring(0, i) + cur.substring(i + 1);
                if (seen.add(next)) line.add(next);
            }
        }
        return result;
    }

    private boolean isValid(String t) {
        int open = 0;
        for (char c : t.toCharArray()) {
            if (c == '(') open++;
            else if (c == ')' && --open < 0) return false;
        }
        return open == 0;
    }
}

This is easy to get right in an interview. But each ring can hold many strings, each costing O(n) to build and check, so it is slower than Way 2 when many removals are needed.

Watch out for

Removing letters. Only brackets may be removed.
Repeated answers. In ()()), removing the ) at index 3 or at index 4 gives the same ()(). Use a set, or skip removing a bracket that equals the one just before it when that one was kept.
Returning [] for )(. The empty string is a valid answer, so return [""].

What interviewers ask next

Return only one valid string, with the fewest removals (LeetCode 1249). Walk left to right dropping unmatched ), then right to left dropping unmatched (. That is O(n), no search.
Just the number of removals. That is openRem + closeRem from the first counting pass.
How do you avoid the set? When removing, skip a bracket if it is the same as the previous character and that previous one was kept. Then each different answer is built exactly once.
What about three kinds of brackets, ()[]{}? Validity needs a stack, and the budget idea still works per kind.

Remember this

Grown-up words: the waiting hands are the open count (a stack depth), the kids who must leave are the minimum removals, the keep or remove tree is backtracking with pruning, and the ring search is breadth first search over strings.