Stack

2 minute read

The Problem

Leetcode 1249. Minimum Remove to Make Valid Parentheses: 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.
Example 4:

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.

The Solution

It’s easy to see that the parentheses are invalid when we have open but does not have respective close and vice versa. Let’s look at an example:

s = "(a(b(c)d)"

There are 3 opens followed by 2 closes, lets call them o1, o2, o3, c1, c2. When we see c1, we match with o3 first since o3 is available (not match with any close yet). When we see c2, we match c2 with o2 since o3 is not available anymore.

The example above tells us that when we iterate the given string from left to right, We will see the order of opens as o1, o2, o3. However, when we check for available open, we check in the reverse orders o3, o2, o1. So how do we store the opens in the order from left to right but we check in reverse order? The answer is to use the stack data structure.

def min_remove_to_make_valid(s):
    stack = []
    for c in s:
        if c != ")":
            stack.append(c)
        else:
            tmp = ""
            while len(stack) > 0 and stack[-1] != "(":
                tmp = stack.pop() + tmp
            
            if len(stack) >0 and stack[-1] == "(":
                tmp = stack.pop() + tmp + c
            stack.append(tmp)
    
    res = ""
    for c in stack:
        # Ensure that open with no close is removed
        if c != "(":
            res += c
            
    return res

The Analysis

Both time and space complexities are linear. Even though there is a while loop in the for loop, every time the characters are popped from stack, they will concatenate into a substring which is pushed back into the stack, and so the number of characters that can be popped out in subsequent while loops will be less, the total operation is no more than the number of characters in the given string, hence the time complexity is O(n).

Similar to queue, the main difficulty part is to recognize the usage of stack, the code will typically be simple and short.

Similar problems:

Updated:

Leave a comment