1249. Minimum Remove to Make Valid Parentheses

MediumStackString

Problem Description

The given problem presents us with a string s that consists of parentheses ('(' and ')') and lowercase English letters. Our goal is to make the string a valid parentheses string by removing the fewest number of parentheses possible. The criteria for a valid parentheses string is:

It is an empty string, or
It contains only lowercase characters, or
It can be written in the form of AB, where A and B are valid strings, or
It can be written in the form of (A), where A is a valid string.

Ultimately, we must ensure that every opening parenthesis '(' has a corresponding closing parenthesis ')', and there are no extra closing parentheses without a matching opening one.

Intuition

The solution can be devised based on the properties of a valid parentheses sequence, where the number of opening '(' and closing ')' parentheses are the same, and at any point in the sequence, there can't be more closing parenthesis before an opening one.

To approach this problem, we need to monitor the balance of the parentheses and remove any excess closing or opening parentheses. A stack can be beneficial in such situations, but this solution optimizes space by using two passes through the string and counting variables to keep track of the balance.

In the first pass, we iterate over the string from left to right, ignoring any characters that are not parentheses. We only add parentheses to the stack if they maintain the balance, but we increment or decrement the counting variable x based on whether we encounter an opening '(' or a closing ')'. This ensures we don't add any extra closing parentheses.

However, after this first pass, we might still have excess opening parentheses, which become evident when looked at from the opposite direction (since they won't have a corresponding closing parenthesis). Hence, we conduct a second pass from right to left, this time using a similar approach to selectively keep valid parentheses and maintaining the count in the opposite manner. By reversing this result, we achieve a string where the parentheses are balanced.

Finally, we combine the characters into a string and return it as the valid parentheses string with the minimal removal of invalid parentheses characters.

Learn more about Stack patterns.

Solution Approach

The solution relies on two main ideas:

Ensuring that every opening parenthesis has a corresponding closing parenthesis to its right.
Ensuring that every closing parenthesis has a corresponding opening parenthesis to its left.

No stack data structure is used to save space; instead, a counter is employed to ensure the balance of parentheses as we iterate through the string.

The algorithm employs two passes:

Left-to-right pass: We iterate through the string, and for each character:
- If it’s a closing parenthesis ')' and the current balance x is zero, we skip adding it to the stack because there's no corresponding opening parenthesis.
- If it's an opening parenthesis '(', we increment the counter x since we have an additional opening parenthesis that needs a match.
- If it's a closing parenthesis ')', we decrement x because we have found a potential match for an earlier opening parenthesis.
- We add all non-parenthesis characters and valid parenthesis characters to stk.

This pass ensures that we don't have unmatched closing parentheses at this stage. However, we may still have unmatched opening parentheses, which the second pass addresses.

Right-to-left pass: We reverse the stk and then iterate through it:
- If it’s an opening parenthesis '(' and the current balance x is zero, we skip adding it to the answer because there's no corresponding closing parenthesis.
- If it's a closing parenthesis ')', we increment the counter x since we need to match it with an opening parenthesis.
- If it's an opening parenthesis '(', we decrement x since we found a match for a closing parenthesis.
- We collect the characters to form the answer, skipping the unmatched opening parentheses.

After this pass, we have a string that contains no unmatched parentheses, and by reversing the result, we get the valid parentheses string.

By only keeping track of the balance of the parentheses and using two linear passes, we efficiently construct a balanced string by ignoring characters that would violate the balance. This approach avoids the overhead of using extra data structures like a stack.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example string s: "a)b(c)d)". We want to remove the fewest number of parentheses to make this a valid parentheses string. Let's apply the solution approach to this string step by step.

Left-to-right pass:

We start with an empty stk and a balance counter x set to 0.
We iterate over each character of the string:
1. 'a' - It is a lowercase letter, so we add it to stk.
2. ')' - The balance x is 0, meaning there's no open parenthesis to match with, so we do not add this to stk.
3. 'b' - It is a lowercase letter, so we add it to stk.
4. '(' - It is an opening parenthesis, so we increment x (x=1) and add it to stk.
5. 'c' - It is a lowercase letter, so we add it to stk.
6. ')' - It is a closing parenthesis, and x is 1, so we decrement x (x=0) and add it to stk.
7. 'd' - It is a lowercase letter, so we add it to stk.
8. ')' - Again, x is 0, so this closing parenthesis does not have a match. We do not add it to stk.

At the end of the first pass, stk is ["a","b","(","c",")","d"], and x is 0.

Right-to-left pass:

We reverse stk to get ["d",")","c","(","b","a"] and set x to 0 again.
Now, we iterate through each character in reverse order:
1. 'a' - It is a lowercase letter, so it remains part of the final string.
2. 'b' - It is a lowercase letter, so it remains part of the final string.
3. '(' - x is 0, so this has no matching closing parenthesis and should be removed.
4. 'c' - It is a lowercase letter, so it remains part of the final string.
5. ')' - It is a closing parenthesis, so we increment x (x=1) and keep it since we expect to find a matching opening parenthesis.
6. 'd' - It is a lowercase letter, so it remains part of the final string.

After reversing the result of this pass, we get "ab(c)d" which indeed is the valid parentheses string after removing the fewest number of parentheses.

This example clearly shows how the two passes effectively remove unnecessary parentheses while keeping the string valid according to the provided criteria.

Solution Implementation

1class Solution:
2    def minRemoveToMakeValid(self, s: str) -> str:
3        # Stack to keep track of characters that lead to a valid string
4        stack = []
5      
6        # Counter to track the balance of parentheses
7        open_count = 0
8      
9        # First pass to remove invalid closing parentheses
10        for char in s:
11            # If a closing parenthesis is encountered with no matching open, skip it
12            if char == ')' and open_count == 0:
13                continue
14            # If an opening parenthesis is found, increment the open count
15            if char == '(':
16                open_count += 1
17            # If a closing parenthesis is found and there is a matching open, decrement the open count
18            elif char == ')':
19                open_count -= 1
20            # Add the character to the stack as it's part of valid substring so far
21            stack.append(char)
22      
23        # Reset the open counter for the second pass
24        open_count = 0
25        # List to store the characters for the final answer
26        answer = []
27      
28        # Second pass to remove invalid opening parentheses; process characters in reverse
29        for char in reversed(stack):
30            # If an opening parenthesis is encountered with no matching close, skip it
31            if char == '(' and open_count == 0:
32                continue
33            # If a closing parenthesis is found, increment the open count
34            if char == ')':
35                open_count += 1
36            # If an opening parenthesis is found and there is a matching close, decrement the open count
37            elif char == '(':
38                open_count -= 1
39            # Add the character to the answer as it is part of a valid substring
40            answer.append(char)
41      
42        # The characters in answer are in reverse order, reverse them back to the correct order
43        return ''.join(reversed(answer))
44

1class Solution {
2    public String minRemoveToMakeValid(String s) {
3        // Use a deque as a stack to manage parentheses.
4        Deque<Character> stack = new ArrayDeque<>();
5        // Counter to keep track of unmatched opening parentheses.
6        int openCount = 0;
7      
8        // First pass: remove invalid closing parentheses.
9        for (int i = 0; i < s.length(); ++i) {
10            char current = s.charAt(i);
11            // Skip this character if it's an unmatched closing parenthesis.
12            if (current == ')' && openCount == 0) {
13                continue;
14            }
15            // If a valid opening parenthesis is found, increment openCount.
16            if (current == '(') {
17                ++openCount;
18            } else if (current == ')') {
19                // If a valid closing parenthesis is found, decrement openCount.
20                --openCount;
21            }
22            // Push the current character onto the stack.
23            stack.push(current);
24        }
25      
26        // StringBuilder to construct the output string.
27        StringBuilder result = new StringBuilder();
28        // Reset openCount for the second pass.
29        openCount = 0;
30      
31        // Second pass: remove invalid opening parentheses.
32        while (!stack.isEmpty()) {
33            char current = stack.pop();
34            // Skip this character if it's an unmatched opening parenthesis.
35            if (current == '(' && openCount == 0) {
36                continue;
37            }
38            // If a closing parenthesis is found, increment openCount.
39            if (current == ')') {
40                ++openCount;
41            } else if (current == '(') {
42                // If an opening parenthesis is found, decrement openCount.
43                --openCount;
44            }
45            // Append the current character to the result.
46            result.append(current);
47        }
48      
49        // Reverse the result string to restore the original order
50        // since the second pass processed characters in reverse.
51        return result.reverse().toString();
52    }
53}
54

1#include <algorithm> // Required for std::reverse
2
3class Solution {
4public:
5    // Function to remove the minimum number of parentheses to make a valid parentheses string.
6    string minRemoveToMakeValid(string s) {
7        string tempStack; // Simulates a stack to hold valid characters.
8        int openCount = 0; // Counter for unmatched '(' characters.
9
10        // First pass: Remove any ')' that doesn't have a matching '('.
11        for (char& c : s) {
12            if (c == ')' && openCount == 0) continue; // Skip invalid ')'.
13            if (c == '(') {
14                openCount++; // Increment counter for '('.
15            } else if (c == ')') {
16                openCount--; // Decrement counter for ')'.
17            }
18            tempStack.push_back(c); // Add the character to the stack.
19        }
20
21        string result; // String that will store the valid parentheses sequence.
22        openCount = 0; // Reset counter for the next pass.
23
24        // Second pass: Remove any '(' that doesn't have a matching ')' from the end.
25        while (!tempStack.empty()) {
26            char c = tempStack.back(); // Take the last character from the stack.
27            tempStack.pop_back(); // Remove that character from the stack.
28          
29            if (c == '(' && openCount == 0) continue; // Skip invalid '('.
30            if (c == ')') {
31                openCount++; // Increment counter for ')'.
32            } else if (c == '(') {
33                openCount--; // Decrement counter for '('.
34            }
35            result.push_back(c); // Add the character to the result string.
36        }
37
38        // The result is built in reverse order, so we need to reverse it.
39        std::reverse(result.begin(), result.end());
40
41        return result; // Return the valid parentheses string.
42    }
43};
44

1function minRemoveToMakeValid(inputString: string): string {
2    // Count how many '(' must be matched.
3    let leftToMatch = 0;
4    // Count how many ')' could be possibly matched.
5    let rightToMatch = 0;
6
7    // First pass to calculate the minimum number of ')' to match
8    for (const char of inputString) {
9        if (char === '(') {
10            // Increment if we find a '(' that potentially could be matched later.
11            leftToMatch++;
12        } else if (char === ')') {
13            // Only increment the rightToMatch if there are unmatched '(' available.
14            if (rightToMatch < leftToMatch) {
15                rightToMatch++;
16            }
17        }
18    }
19
20    // Reset the count of '(' that has been matched so far.
21    let matchedLeftCount = 0;
22    // Initialize the result string to be built.
23    let result = '';
24
25    // Second pass to build the result string with matched parentheses
26    for (const char of inputString) {
27        if (char === '(') {
28            // If we still have '(' that can be matched, we take it and add to the result string.
29            if (matchedLeftCount < rightToMatch) {
30                matchedLeftCount++;
31                result += char;
32            }
33        } else if (char === ')') {
34            // If there is a '(' we can match with, we include the ')' in the result.
35            if (matchedLeftCount !== 0 && rightToMatch !== 0) {
36                rightToMatch--;
37                matchedLeftCount--;
38                result += char;
39            }
40        } else {
41            // For any character that is not a parenthesis, we always include it in the result.
42            result += char;
43        }
44    }
45
46    // Return the final result string with all valid matched parentheses.
47    return result;
48}
49

Time and Space Complexity

The given Python code processes a string s to remove the minimum number of parentheses to make the input string valid (all opened parentheses must be closed). The code uses two passes through the string, forward and backward, utilizing stacks to keep track of parentheses and a counter to validate them.

Time Complexity

The time complexity of this algorithm is O(n), where n is the length of the string s.

It performs two separate passes through the string:

The first for-loop iterates through each character of the input string once to count the parentheses and remove invalid closing parentheses.
After the first loop, the stack stk contains a modified version of the string without excess closing parentheses.
The second for-loop iterates through the modified string (stack stk) in reverse, again once for each element, to count the parentheses in the reverse direction and remove the invalid opening parentheses.

Each character is processed once in each direction, resulting in a total of 2 * n operations, which simplifies to O(n) as constants are dropped in Big O notation.

Space Complexity

The space complexity of the code is also O(n), due to the use of additional data structures that store elements proportional to the size of the input string.

The stk list is used to store the characters of the string after the first pass. In the worst case, it could store the entire string if no closing parentheses need to be removed, leading to O(n) space.
The ans list is used to store the characters after the second pass has checked for the validity of the remaining opening parentheses. Similarly, in the worst case, it could store the entire string if no opening parentheses need to be removed, also leading to O(n) space.

Even though we use two stacks (stk and ans), they do not exist at the same time, as ans is only created after stk's processing is completed. Therefore, we don't consider this as 2n but simply n, and the space complexity remains O(n).

Note: The space needed for counters and individual characters is constant and therefore is not included in the space complexity analysis. The space complexity is determined by the significant data structures that grow with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don't know