Problem explanation

The problem at hand requires us to make the given string s a valid parentheses string by removing the minimum number of characters. The string s consists of parentheses ('(' and ')') and lowercase English characters. A string is considered a valid parentheses string if:

1. It is an empty string.
2. It only contains lowercase characters.
3. It can be divided into two partitions: AB, where A and B are valid strings.
4. It can be represented as (A), where A is a valid string.

The main challenge here is coming up with a strategy to determine which parentheses or character we should remove while ensuring that we remove the minimum number of characters possible.

Approach

We'll use a stack to solve this problem. We'll iterate over the string s from left to right while maintaining the indices of all unpaired open parentheses in the stack:

1. If we find an open parenthesis '(', we add the current index to the stack (indicatively marking it as unpaired).
2. If we find a closing parenthesis ')', we pop the top index from the stack if it's not empty (indicatively marking it as paired). If the stack is empty, it means we've stumbled upon an unpaired closing bracket, which we should mark for removal.

At the end of this process, every index left in the stack will be an unpaired open parenthesis and thus should also be marked for removal. Finally, we create a new string excluding all the marked characters.

Example

Let's take an example string s = "lee(t(c)o)de)". As per our approach:

1Step 1: initialize our stack
2
3Step 2: iterate over s:
4    - for i=0, s[i]='l', it's a lowercase English character, do nothing.
5    - for i=1, s[i]='e', it's a lowercase English character, do nothing.
6    - for i=2, s[i]='e', it's a lowercase English character, do nothing.
7    - for i=3, s[i]='(', it's an open brace, add it to stack. Stack=[3]
8    - for i=4, s[i]='t', it's a lowercase English character, do nothing.
9    - for i=5, s[i]='(', it's an open brace, add it to stack. Stack=[3, 5]
10    - for i=6, s[i]='c', it's a lowercase English character, do nothing.
11    - for i=7, s[i]=')', it's a close brace, pop from stack. Stack=[3]
12- and we continue this process through the end of the string s.

In the end, we get stack = [12], so we understand that 12th index currently in our string s needs to be removed.

Note

The stack data structure is utilized here, as it fits perfectly for solving this problem due to its Last-In-First-Out (LIFO) nature which is suitable for tracking open and close braces in a proper manner.

Now let's translate our approach into different popular programming languages.

Python Solution

In Python, we can use the list data structure as a stack.

1
2python
3class Solution:
4    def minRemoveToMakeValid(self, s: str) -> str:
5        stack = []
6        s = list(s)
7        for i, char in enumerate(s):
8            if char == '(':
9                stack.append(i)
10            elif char == ')':
11                if stack:
12                    stack.pop()
13                else:
14                    s[i] = ''
15        while stack:
16            s[stack.pop()] = ''
17        return ''.join(s)

Java Solution

1
2java
3class Solution {
4    public String minRemoveToMakeValid(String s) {
5        StringBuilder sb = new StringBuilder(s);
6        Stack<Integer> stack = new Stack<>();
7        for(int i=0; i<sb.length(); ++i) {
8            if(sb.charAt(i) == '(')
9                stack.add(i);
10            else if(sb.charAt(i) == ')') {
11                if(!stack.empty()) 
12                    stack.pop();
13                else 
14                    sb.setCharAt(i, '*');
15            }
16        }
17        while(!stack.empty())
18            sb.setCharAt(stack.pop(), '*');
19        return sb.toString().replaceAll("\\*", "");
20    }
21}

JavaScript Solution

1
2javascript
3var minRemoveToMakeValid = function(s) {
4    const stack = [];
5    s = s.split('');
6    for(let i = 0; i < s.length; i++) {
7        if(s[i] === '(') {
8            stack.push(i);
9        } else if(s[i] === ')') {
10            if(stack.length) {
11                stack.pop();
12            } else {
13                s[i] = '';
14            }
15        }
16    }
17    while(stack.length) {
18        s[stack.pop()] = '';
19    }
20    return s.join('');
21};

C++ Solution

1
2cpp
3class Solution {
4public:
5    string minRemoveToMakeValid(string s) {
6        stack<int> stk;
7        for (auto i = 0; i < s.size(); ++i) {
8            if (s[i] == '(') stk.push(i);
9            if (s[i] == ')') {
10                if (!stk.empty()) stk.pop();
11                else s[i] = '*';
12            }
13        }
14        while (!stk.empty()) {
15            s[stk.top()] = '*';
16            stk.pop();
17        }
18        s.erase(remove(s.begin(), s.end(), '*'), s.end());
19        return s;
20    }
21};

C# Solution

1
2csharp
3public class Solution {
4    public string MinRemoveToMakeValid(string s) {
5        var sb = new StringBuilder(s);
6        var stack = new Stack<int>();
7        for (var i = 0; i < sb.Length; ++i) {
8            if (sb[i] == '(') {
9                stack.Push(i);
10            } else if (sb[i] == ')') {
11                if (stack.Count > 0) {
12                    stack.Pop();
13                } else {
14                    sb[i] = '*';
15                }
16            }
17        }
18        while (stack.Count > 0) {
19            sb[stack.Pop()] = '*';
20        }
21        return sb.ToString().Replace("*", "");
22    }
23}

In all the above solutions, we use a Stack data structure to store indices of unpaired open parentheses and a StringBuilder / list to store our string s for easy modification. The solutions in all these languages follow the same logic and algorithm. The only difference is in syntax and the use of language specific functions.# Conclusion

We have successfully developed a solution that can remove the minimum number of parentheses to make a string valid. The solution uses a stack data structure, which accordingly stores the indices of the open parentheses and iteratively checks if they can be paired correctly. The unpaired parentheses are then removed from the string to yield a valid string.

This algorithm is efficient and works in O(n) time, where n is the length of the string. For every opening and closing bracket, we simply push or pop from our stack. This algorithm is also memory efficient, requiring O(n) extra space for the stack.

Though this problem might seem complicated at first, with a good understanding of data structures it is easy to solve. It also is a good example of when stack data structure can be helpful.

The solutions in different languages might seem different in terms of syntax but all follow the same logic flow and use the same underlying algorithm. The choice of language should not limit us from solving these problems effectively.

This same problem solving approach can be extended to similar problems where we have to track opening and closing of similar pairs and it's not just confined to parentheses (opening - closing brackets).

The key take-away from this article is that with the right understanding and manipulation of data structures, complicated problems can be solved more effectively and efficiently.