Problem statement

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.

Example 2:
Input: s = “a)b(c)d”
Output: “ab(c)d”

Example 3:
Input: s = “))(("
Output: “"
Explanation: An empty string is also valid.

Example 4:
Input: s = “(a(b(c)d)"
Output: “a(b(c)d)”

Constraints:

  • 1 <= s.length <= 10^5
  • s[i] is one of ‘(’ , ‘)’ and lowercase English letters.

Ideas

It is common to use stack for solving parentheses related problems. We typically push left parentheses to the stack and pop up when it matches right parentheses.

This problem is little bit different because it contains characters which are not just parentheses. The returned result is not the length of the valid string but rather the actual string representation.

We need a way to record the positions of parentheses to be removed, hashset fits well here. Bascially, we apply the greedy strategy and track parentheses that causes the string not being palindrome. We call them “bad parentheses”.

The pseudocode is like:

let s be stack
let bad be hash set
iterate input string for each char
   if char == '(':
      push to stack
   else if char == ')':
      if stack is empty:
          add char to bad
      else
         pop from stack
add all remaining in stack to bad

build result and skip char in bad

Solution

class Solution {
    public String minRemoveToMakeValid(String s) {
        Set<Integer> toDelete = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else if (s.charAt(i) == ')') {
                if (stack.isEmpty()) {
                    toDelete.add(i);
                } else {
                    stack.pop();
                }
            }
        }
        while (!stack.isEmpty()) {
            toDelete.add(stack.pop());
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (toDelete.contains(i)) {
                continue;
            }
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}