Minimum Remove to Make Valid Parentheses - LeetCode
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 <= 105
s[i] is either'(' , ')', or lowercase English letter.
- code
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
res = []
count = 0
for c in s:
if c.isalpha():
res.append(c)
elif c == '(':
count += 1
res.append(c)
elif c == ')' and count != 0:
res.append(c)
count -= 1
res.reverse()
while count != 0:
res.remove('(')
count -= 1
res.reverse()
return "".join(res)
- code
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
# Pass 1: Remove all invalid ")"
first_pass_chars = []
balance = 0
open_seen = 0
for c in s:
if c == "(":
balance += 1
open_seen += 1
if c == ")":
if balance == 0:
continue
balance -= 1
first_pass_chars.append(c)
# Pass 2: Remove the rightmost "("
result = []
open_to_keep = open_seen - balance
for c in first_pass_chars:
if c == "(":
open_to_keep -= 1
if open_to_keep < 0:
continue
result.append(c)
return "".join(result)