public int remove(char input[]){
        if(input == null){
            return 0;
        }
        Deque<Integer> dq = new LinkedList<Integer>();
        for(int i=0; i < input.length; i++){
            //skip non bracket characters
            if(input[i] != '(' && input[i] != ')'){
                continue;
            }
            
            //add opening brackets
            if(input[i] == '('){
                dq.addFirst(i);
            }
            else if(input[i] == ')'){
                //if top is opening bracket just remove from stack else add closing bracket
                if(!dq.isEmpty() && input[dq.peekFirst()] == '('){
                    dq.pollFirst();
                }else{
                    dq.addFirst(i);
                }
            }
        }
        int index = 0;
        //iterate through list again and don't add leftover
        //characters from stack in final result
        for(int i=0; i < input.length; i++){
            if(!dq.isEmpty() && i == dq.peekLast()) {
                dq.pollLast();
            }else {
                input[index++] = input[i];
            }
        }
        return index;
    }
Date 03/17/2015
@author tusroy

Given a string with unbalanced brackets how do you remove minimum number
of extra brackets so that you are left with balanced brackets in the string

e.g )( -> empty string
    (a) -> (a)
    ((mnq)abc))) -> ((mna)abc)
    (abc)(( -> (abc)

Solution 1
Keep a stack. When non bracket character shows up just skip it.
When an opening bracket shows up just add it.
When closing bracket shows up, see if top of stack is opening bracket. If yes
then just remove that from stack else add closing bracket into the stack.

Solution 2
This can be done without stack as well. Keep count of open and close brackets.
Any time closeBracket gets more than openBracket do not put it in result.
After we are done iterating input again if openBracket is more than closeBracket
get rid of last (openBracket-closeBracket) open brackets.

Test cases:
empty string
String with )(
String with all opening brackets
String with all closing brackets
String with mix of open close brackets and characters between them
String with already balanced parenthesis
src/com/interview/stackqueue/RemoveExtraBrackets.java