1249. Minimum Remove to Make Valid Parentheses
https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses
Description
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 withB
), whereA
andB
are valid strings, orIt can be written as
(A)
, whereA
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 <= 105
s[i]
is either'('
,')'
, or lowercase English letter.
ac
class Solution {
public String minRemoveToMakeValid(String s) {
// Edge cases
if (s == null || s.length() == 0) return s;
Stack<Integer> left = new Stack<>();
Stack<Integer> right = new Stack<>();
HashSet<Integer> toRemove = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left.push(i);
} else if (s.charAt(i) == ')') {
right.push(i);
}
if (right.size() > left.size()) {
toRemove.add(right.pop());
}
}
while (left.size() > right.size()) {
toRemove.add(left.pop());
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (toRemove.contains(i)) continue;
sb.append(s.charAt(i));
}
return sb.toString();
}
}
// O(N) time, O(N) space. Parentheses->left&right. Similar to # 022-Generate Parentheses.
Last updated
Was this helpful?