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 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.
Constraints:
1 <= s.length <= 105s[i] is either '(' , ')', or lowercase English letter.
Solutions
Solution 1: Two Passes
First, we scan from left to right and remove the extra right parentheses. Then, we scan from right to left and remove the extra left parentheses.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
Similar problems:
PythonJavaC++GoTypeScriptRust
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
stk = []
x = 0
for c in s:
if c == ')' and x == 0:
continue
if c == '(':
x += 1
elif c == ')':
x -= 1
stk.append(c)
x = 0
ans = []
for c in stk[::-1]:
if c == '(' and x == 0:
continue
if c == ')':
x += 1
elif c == '(':
x -= 1
ans.append(c)
return ''.join(ans[::-1])(code-box)
class Solution {
public String minRemoveToMakeValid(String s) {
Deque<Character> stk = new ArrayDeque<>();
int x = 0;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (c == ')' && x == 0) {
continue;
}
if (c == '(') {
++x;
} else if (c == ')') {
--x;
}
stk.push(c);
}
StringBuilder ans = new StringBuilder();
x = 0;
while (!stk.isEmpty()) {
char c = stk.pop();
if (c == '(' && x == 0) {
continue;
}
if (c == ')') {
++x;
} else if (c == '(') {
--x;
}
ans.append(c);
}
return ans.reverse().toString();
}
}(code-box)
class Solution {
public:
string minRemoveToMakeValid(string s) {
string stk;
int x = 0;
for (char& c : s) {
if (c == ')' && x == 0) continue;
if (c == '(')
++x;
else if (c == ')')
--x;
stk.push_back(c);
}
string ans;
x = 0;
while (stk.size()) {
char c = stk.back();
stk.pop_back();
if (c == '(' && x == 0) continue;
if (c == ')')
++x;
else if (c == '(')
--x;
ans.push_back(c);
}
reverse(ans.begin(), ans.end());
return ans;
}
};(code-box)
func minRemoveToMakeValid(s string) string {
stk := []byte{}
x := 0
for i := range s {
c := s[i]
if c == ')' && x == 0 {
continue
}
if c == '(' {
x++
} else if c == ')' {
x--
}
stk = append(stk, c)
}
ans := []byte{}
x = 0
for i := len(stk) - 1; i >= 0; i-- {
c := stk[i]
if c == '(' && x == 0 {
continue
}
if c == ')' {
x++
} else if c == '(' {
x--
}
ans = append(ans, c)
}
for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
ans[i], ans[j] = ans[j], ans[i]
}
return string(ans)
}(code-box)
function minRemoveToMakeValid(s: string): string {
let left = 0;
let right = 0;
for (const c of s) {
if (c === '(') {
left++;
} else if (c === ')') {
if (right < left) {
right++;
}
}
}
let hasLeft = 0;
let res = '';
for (const c of s) {
if (c === '(') {
if (hasLeft < right) {
hasLeft++;
res += c;
}
} else if (c === ')') {
if (hasLeft != 0 && right !== 0) {
right--;
hasLeft--;
res += c;
}
} else {
res += c;
}
}
return res;
}(code-box)
impl Solution {
pub fn min_remove_to_make_valid(s: String) -> String {
let bs = s.as_bytes();
let mut right = {
let mut left = 0;
let mut right = 0;
for c in bs.iter() {
match c {
&b'(' => {
left += 1;
}
&b')' if right < left => {
right += 1;
}
_ => {}
}
}
right
};
let mut has_left = 0;
let mut res = vec![];
for c in bs.iter() {
match c {
&b'(' => {
if has_left < right {
has_left += 1;
res.push(*c);
}
}
&b')' => {
if has_left != 0 && right != 0 {
right -= 1;
has_left -= 1;
res.push(*c);
}
}
_ => {
res.push(*c);
}
}
}
String::from_utf8_lossy(&res).to_string()
}
}(code-box)
