The Problem

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of  '(' 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)"

Problem Solving Approach

We will identify what we are given, what we need to return and break down a method to get from point A to B in small steps. Then we will combine those steps to form the full solution.

Given

We are given a string of characters that can include any combination of letters, '(', and ')'.

Return

We return a string. This string will either be identical to the input string or it will be identical with the exception of certain '(' and ')' removed. No letter will ever be modified. No character will ever be added. Any open parenthesis will be removed if there is not a corresponding closing parenthesis. Any closing parenthesis will be removed if there is not a corresponding opening parenthesis.

Methods

There are two ways to approach this problem that have the same time and space complexity: The stack approach and an approach I will call the 'Counter Approach'.

The Stack Approach

A stack is a useful data structure that allows you to place data in a stack and then take it off the top of the stack at a later time. This guide will give a simple example of a way it can be implemented.

The Set Up

This problem calls for a modified version of the input string to be returned. It is important to know that strings cannot be modified in place. New strings can be created to replace old strings, but they cannot be modified. Lists, on the other hand, offer much more flexibility in modification. So, we first convert the string into a list, with plans of converting it back into a string at the end. Simply done like this:

# S is the input string

# at the beginning
S = list(S)
# 'abc' will turn into ['a', 'b', 'c']

# at the end
''.join(S)
# ['a', 'b', 'c'] will turn into 'abc'

As stated in the 'Return' section, the only modifications we will ever make is the removal of items. With our string as a list, we can easily replace any value that needs to be removed with an empty string. This removes it without changing the index of any other item.

Identifying Valid Parenthesis Pairs

Since we need to create a string with a balanced set of parenthesis with the minimum number of changes, we must first identify parentheses pairs that already open and close properly, and therefore do not need to be removed.

This approach uses the stack to store the indices of instances of '('. As the list is traversed, instances of '(' trigger that index to be added to the stack. This is essentially creating a pile or 'stack' of the indices of unclosed open parentheses. Instances of ')' will trigger the value on the top of the stack to be removed since it means we have found a closing parenthesis for a currently unclosed open parenthesis.

So as a loop traverses the input, '(' adds its index to the stack and ')' removes items from the stack. Here is what this would look like:

        S = list(S)
        stack = []
        for i, c in enumerate(S):
            if c == ")": stack: stack.pop()
            elif c == "(": stack.append(i)
        "".join(S)

Removing Extra ')'

The stack finds us valid parenthesis pairs. However, it can also be used to remove extra opening parentheses. If at any point, we come across an open parenthesis while the stack is empty, this means there is nothing for it to close and it is an extra ')'. So, we can simply remove it. With this added check, the stack looks like this:

        S, stack = list(S), []
        for i, c in enumerate(S):
            if c == ")":
                if stack: stack.pop()
                else: S[i] = ""
            elif c == "(": stack.append(i)
        "".join(S)

Removing Extra '('

Since this list isn't sorted in any way, there is no way to know if all open parentheses will be closed until the entire list is traversed. After a full traversal, any item that remain in the stack represents an unclosed open parenthesis. Knowing this, we can now add a second loop that simply traverses the stack and, at every iteration, turns the unclosed parenthesis into an empty string. With this, we have the full solution:

Stack Approach Solution

    def minRemoveToMakeValid(S):
        S, stack = list(S), []
        for i, c in enumerate(S):
            if c == ")":
                if stack: stack.pop()
                else: S[i] = ""
            elif c == "(": stack.append(i)
        for i in stack: S[i] = ""
        return "".join(S)

Time Complexity

N will represent the length of the input string. The first for loop traverses the length of the input string. It runs in O(N) in every case. The second for loop traverses the stack. It runs in O(N) in the worst case where the string is entire made up of '(' and the string looks something like this: '(((((((((((((('. Since there is only ever a single O(N) loop running at any time, the time complexity is O(N).

Space Complexity

Turning the string into a list immediately uses O(N) space where N represents the length of the string. The stack uses O(N) space in the worst case. Similar to the time complexity, it can store the entire string if the string is all '('. Unlike the time complexity, all of this space will be used at the same time, making it O(2N) space. However, this can be simplified so the space complexity is O(N).

The Counter Approach

The main differences between this approach and the stack approach is that this approach keeps the string as a string instead of turning it into a list and uses a simple counter instead of a stack to track unclosed parenthesis. Other than that, it works in a very similar way. Since it is so similar, it will be best for me to provide the full solution and just explain the key differences since walking through the steps would be repetitive.

Counter Approach Solution

def minRemoveToMakeValid(S):
    counter = 0 # track the number of unclosed open parentheses
    i = 0 # tracks the current index in the loop
    while i < len(S): # loops through the string
        if S[i] == '(': counter += 1 # increments the counter at instances of '('
        if S[i] == ')':
            if counter != 0: 
              counter-=1 # decrements the counter at instances of ')'
            else: # if the counter is 0
              S = S[:i] + S[i+1:] # remove what is at the current index
              i-=1 # move the current index back one so we can do another check there since there will be a new value
        i+=1 # iterate through the string
    i = len(S) - 1 # prepare i for the second loop
    while counter > 0: # loop backwards through the string until the counter is zero and there are no more unclosed parentheses
        if S[i] == '(': # when we find a '('
            S = S[:i] + S[i+1:] # remove it
            counter-=1 # lower the counter
        i-=1 # iterate through the string
    return S

The trickiest part of the this solution is likely to know that the index needs to be decremented when removing an ')' since it is sliced out and shifting the index of the rest of the string. This does not need to be done in the reverse loop since the index is only shifting for the values that have already been checked.

Time Complexity

Similar to the stack approach, this approach includes two loops, each with a number of iterations that depends on the length of the input string. They do not happen at the same time, so if N is the length the input string, this solution runs in O(N) time.

Space Complexity

If strings could be modified in place like lists, this solution could hypothetically run in O(1) since all we ever do is slice items out of the string. But in reality, every time we slice a value out a string, we are creating a new string. So if N is the length of the string, this solution runs in O(N) space.