1249. Minimum Remove to Make Valid Parentheses (Python)

Related Topic

Stack.

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.

Sample I/O

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.

Example 4

Input: s = "(a(b(c)d)"
Output: "a(b(c)d)"

Note

1. 1 <= s.length <= 10^5
2. s[i] is one of ‘(‘ , ‘)’ and lowercase English letters.

Methodology

We need a stack to store all “(“’s index, and once we meet “)”, we will pop out index from stack. There are special cases: If the stack is empty and we meet “(“ then we store the index into tmp set. The tmp set will store all index that need to remove. If after the iteration, the stack still has “(“, then we store all index of stack into tmp set. Then we start iterate the string again, we will only keep the character which index is not in tmp set.

def minRemoveToMakeValid(self, s: str) -> str:
        stack=[]
        indexes_to_remove = set()
        res = ''
        for i, c in enumerate(s):
            if c not in '()':
                continue
            if c == '(':
                stack.append(i)
            elif not stack:
                indexes_to_remove.add(i)
            else:
                stack.pop()
        indexes_to_remove = indexes_to_remove.union(set(stack))
        for i, c in enumerate(s):
            if i not in indexes_to_remove:
                res+=c
        return res

BigO

We iterate the string twice so the total cost will be O(n)