1249. Minimum Remove To Make Valid Parentheses

/**

 * 1249. Minimum Remove to Make Valid Parentheses

 * Given a string s of ‘(‘ , ‘)’ and lowercase English characters.

 * Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions )

 * so that the resulting parentheses string is valid and return any valid string.

 * Formally, a parentheses string is valid if and only if:

 * It is the empty string, contains only lowercase characters, or

 * It can be written as AB (A concatenated with B), where A and B are valid strings, or

 * It can be written as (A), where A is a valid string.

 * Example 1:

 * Input: s = “lee(t(c)o)de)”

 * Output: “lee(t(c)o)de”

 * Explanation: “lee(t(co)de)” , “lee(t(c)ode)” would also be accepted.

 */

See solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/ParenthesisRemove.java

This is a very common interview question. I have included the solution below as it’s a very elegant way to solve this problem.

Algorithm is:

• Create a stack for open parenthesis and a list for unmatched closed parenthesis
• Iterate through characters in the string left to right
• When an open parenthesis is found add it to stack
• When a closed parenthesis is found
  • If open stack is not empty, pop one from open stack
  • Otherwise add closed index to the closed list
• Add any remaining items in open stack to the closed list
• Sort the items in closed list in reverse order (highest index first)
• Copy string to string builder so you can adjust it efficiently
• Iterate through the closed list which now has highest indexes first
  • Delete characters from the string builder (deleting highest first so that order of items in the string builder stays consistent).

Here is the code:

public String minRemoveToMakeValid(String s) {
    Stack<Integer> stackOpen = new Stack<>();
    List<Integer> close = new ArrayList<>();
    //do regular stack processing
    for (int i =0; i < s.length(); i++) {
        if(s.charAt(i)=='(') {
            stackOpen.push(i);
        } else if (s.charAt(i) == ')') {
            if (stackOpen.isEmpty()) {
                close.add(i); //these need to be removed so add them to a separate collection
            } else {
                stackOpen.pop();
            }
        }
    }
    //merge open with close in same collection
    while (!stackOpen.isEmpty()) {
        close.add(stackOpen.pop());
    }
    //sort reverse , delete chars from end to beginning so that your indexes stay consistent
    Collections.sort(close, (a, b) -> b - a);
    //java string are immutable, so copy them to string builder and then modify
    StringBuilder builder = new StringBuilder(s);
    for (Integer i : close) {
        builder.deleteCharAt(i);
    }
    return builder.toString();
}