1249. Minimum Remove to Make Valid Parentheses #

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.

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.

Problem Summary #

Given a string s consisting of ‘('、')’ and lowercase letters. You need to remove the minimum number of ‘(’ or ‘)’ (parentheses can be removed from any positions) from the string so that the remaining “parentheses string” is valid. Return any valid string. A valid “parentheses string” should satisfy any one of the following requirements:

An empty string or a string containing only lowercase letters
A string that can be written as AB (A concatenated with B), where both A and B are valid “parentheses strings”
A string that can be written as (A), where A is a valid “parentheses string”

Solution Ideas #

The easiest idea to think of is to use a stack to determine whether the parentheses matching is valid. This approach is feasible, and the time complexity is only O(n).
Without using a stack, you can traverse in 2 passes: traverse forward once to mark the extra '(', then traverse backward once to mark the extra ')', and finally delete all these characters marked as extra. The code for this solution is also very concise, and the time complexity is also O(n).
Improve the above solution a bit. During the forward traversal, not only can the extra '(' be marked, but the extra ')' can also be removed along the way. This way, only one loop is needed. Finally, delete the extra '('. The time complexity is still O(n).

Code #

package leetcode

func minRemoveToMakeValid(s string) string {
	res, opens := []byte{}, 0
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			opens++
		} else if s[i] == ')' {
			if opens == 0 {
				continue
			}
			opens--
		}
		res = append(res, s[i])
	}
	for i := len(res) - 1; i >= 0; i-- {
		if res[i] == '(' && opens > 0 {
			opens--
			res = append(res[:i], res[i+1:]...)
		}
	}
	return string(res)
}