| comments | difficulty | edit_url | rating | source | tags | ||
|---|---|---|---|---|---|---|---|
true |
Medium |
1657 |
Weekly Contest 161 Q3 |
|
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(Aconcatenated withB), whereAandBare valid strings, or - It can be written as
(A), whereAis 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.
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
Similar problems:
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])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();
}
}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;
}
};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)
}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;
}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()
}
}