min_remove_valid_parentheses.py (1166B)
| # 1249. Minimum Remove to Make Valid Parentheses
"""
given a string s of '(' and ')' and lowercase english characters. your task
is to remove the minimum number of parentheses 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 where A and B are valid
strings, or it can be written as (A) where A is a valid string.
"""
class Solution(object):
def minRemoveToMakeValid(self, s):
"""
:type s: str
:rtype: str
"""
s = list(s)
stack = []
for i, c in enumerate(s):
if c == "(":
stack.append(i)
elif c == ")":
if stack:
stack.pop()
else:
s[i] = ""
while stack:
s[stack.pop()] = ""
return "".join(s)
if __name__ == "__main__":
obj = Solution()
print(obj.minRemoveToMakeValid(s="lee(t(c)o)de)"))
print(obj.minRemoveToMakeValid(s="a)b(c)d"))
print(obj.minRemoveToMakeValid(s="))(("))
|
