Minimum Remove to Make Valid Parentheses — LeetCode 1249 Python Solution

The problem

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.

Example

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.

Python solution

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])

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 1249. Minimum Remove to Make Valid Parentheses is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems