Leetcode 301 - Java BFS - pruning idea

Leetcode301_JavaBFS_Pruning.java

/*
Leetcode 301: remove invalid parentheses

Study one of discussion how to apply BFS and also pruning techniques. 

Study is based on the discussion here:
https://leetcode.com/problems/remove-invalid-parentheses/discuss/75041/Java-BFS-solution-16ms-avoid-generating-duplicate-strings

What I like to do is to rewrite the notes and then try to understand better the content. 
And also I like to learn code techniques to handle special edge case, and then apply to 
my problem solving later. 

Here is the notes:
https://leetcode.com/problems/remove-invalid-parentheses/discuss/75041/Java-BFS-solution-16ms-avoid-generating-duplicate-strings

The naive BFS solution is quite simple to implement. To speed up we can use a Set to record all 
the strings generated and avoid revisit. But a better and faster solution is to avoid generate 
duplicate strings all together.

Several facts are listed in the following orders.

**Remove first char in consecutive ones**

First when a ‘)’ or ‘(’  is removed from several consecutive ones, only remove the first one.
Because removing any one the result will be the same. For example:
"())" ---> "()"
only remove the first one ')' of '))'

**the order is matter? **
A character is removed only it must behind it’s parent removal position. 

For example, we need remove 2 from "(())(("

we want to remove positions combination i, j with no duplicate so we let i < j then 
it will not generate duplicate combinations in practice, we record the position i and 
put it in to queue which is then polled out and used as the starting point of the next 
removal. 

**all removal are in [)]+[(]+ format **
If the previous step a '(' is removed, a ')' will never be removed in the following steps. 
In other words, the removals are in the format of the following:
")))))))))((((((((("

All the removed characters is consecutive left bracket followed by consecutive right bracket.

Add those above 3 facts, we can avoid generate duplicate strings and the need of a set which 
saves a lot of space.

Ultimately we can further improve the algorithm to eliminate isValid calls. To do this we 
need to remove and only remove those characters that would lead us to valid strings. This 
needs some preprocess and can reduce the time to around 3ms.
*/
public List<String> removeInvalidParentheses(String s) {
    if (isValid(s))
        return Collections.singletonList(s);
    List<String> ans = new ArrayList<>();
    //The queue only contains invalid middle steps
    Queue<Tuple> queue = new LinkedList<>();
    //The 3-Tuple is (string, startIndex, lastRemovedChar)
    queue.add(new Tuple(s, 0, ')'));
    while (!queue.isEmpty()) {
        Tuple x = queue.poll();
        //Observation 2, start from last removal position
        for (int i = x.start; i < x.string.length(); ++i) {
            char ch = x.string.charAt(i);
            //Not parentheses
            if (ch != '(' && ch != ')') continue;
            //Observation 1, do not repeatedly remove from consecutive ones
            if (i != x.start && x.string.charAt(i - 1) == ch) continue;
            //Observation 3, do not remove a pair of valid parentheses
            if (x.removed == '(' && ch == ')') continue;
            String t = x.string.substring(0, i) + x.string.substring(i + 1);
            //Check isValid before add
            if (isValid(t))
                ans.add(t);
            //Avoid adding leaf level strings
            else if (ans.isEmpty())
                queue.add(new Tuple(t, i, ch));
        }
    }
    return ans;
}

public static boolean isValid(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); ++i) {
        char c = s.charAt(i);
        if (c == '(') ++count;
        if (c == ')' && count-- == 0) return false;
    }
    return count == 0;
}

private class Tuple {
    public final String string;
    public final int start;
    public final char removed;

    public Tuple(String string, int start, char removed) {
        this.string = string;
        this.start = start;
        this.removed = removed;
    }
}