Problem 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.

Example 1:

1
2
3
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:

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

Example 3:

1
2
3
Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Example 4:

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

Constraints:

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

Solution:

  1. Convert string to list, because String is an immutable data structure in Python and it’s much easier and memory-efficient to deal with a list for this task.
  2. Iterate through list
  3. Keep track of indices with open parentheses in the stack. In other words, when we come across open parenthesis we add an index to the stack.
  4. When we come across close parenthesis we pop an element from the stack. If the stack is empty we replace current list element with an empty string
  5. After iteration, we replace all indices we have in the stack with empty strings, because we don’t have close parentheses for them.
  6. Convert list to string and return
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        # stack to keep parentheses
        s = list(s)
        stk = deque()
        
        for i, char in enumerate(s):
            if char == '(':
                stk.append(i)
            elif char == ')':
                if stk:
                    stk.pop()
                else:
                    s[i] = ''
        while stk:
            s[stk.pop()] = ''
        return ''.join(s)

time complexity: $O()$
space complexity: $O()$
reference:
related problem: