Problem

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.

Examples

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.

Solution

In the problem, when we see ) before (, that has to go for sure. For eg. )( will return in "". But other than that, we have to somehow have equal count of ( and ).

Method 1 - Using Stack

We can use stack of indices. To make the string valid with minimum removals, we need to get rid of all parentheses that do not have a matching pair.

  1. Push char index into the stack when we see '('.
  2. Pop from the stack when we see ')'.
    • If the stack is empty, then we have ')' without the pair, and it needs to be removed.
  3. In the end, the stack will contain indexes of '(' without the pair, if any. We need to remove all of them too. We can use boolean array to keep track of it.

Code

Java
public String minRemoveToMakeValid(String s) {
	int len = s.length();
	boolean[] b = new boolean[s.length()];
	StringBuilder res = new StringBuilder("");
	Stack<Integer> st = new Stack<Integer> ();
	for (int i = 0; i<len; ++i) {
		if (s.charAt(i) == '(') {
			st.push(i);
		} else if (s.charAt(i) == ')') {
			if (!st.isEmpty()) {
				// match these pairs, all unmatched are false anyway
				b[i] = true;
				b[(int) st.pop()] = true;
			}
		} else {
			b[i] = true; // any character other than ( and ) are true anyway
		}
	}

	for (int i = 0; i<len; ++i) {
		if (b[i]) {
			res.append(s.charAt(i));
		}
	}

	return res.toString();
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 2 - Using Counters

We can keep track of 2 counters - open and close for the respective parenthesis. However, we can just increment open when we see ( and decrement when we see ).

We can use StringBuilder for adding chars to string.

  • Whenever we see the case where open is 0, but there is a ), we can skip adding it to valid string.
  • What if open stays more than 0 after the first loop finishes? We can loop backward to fix it. Why loop from end? - Because take for eg. ()(, then it is better to delete last ( unbalanced ( rather than first one, as that will result in invalid string )(. What we want is ()

Code

Java
public String minRemoveToMakeValid(String s) {
	int open = 0;
	int close = 0;
	StringBuilder sb = new StringBuilder();
	for (char c: s.toCharArray()) {
		if (c == '(') {
			open++;
		} else if (c == ')') {
			if (open == 0) {
				continue;
			}
			open--;
		}

		sb.append(c);
	}

	StringBuilder ans = new StringBuilder();
	for (int i = sb.length() - 1; i >= 0; i--) {
		if (sb.charAt(i) == '(' && open--> 0) {
			continue;
		}
		ans.append(sb.charAt(i));
	}

	return ans.reverse().toString();
}