Code Implementation

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        s = list(s)
        stack = []
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            elif c == ')':
                if stack:
                    stack.pop()
                else:
                    s[i] = ''
        while stack:
            s[stack.pop()] = ''
        return ''.join(s)
      

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        vector<int> stack;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') stack.push_back(i);
            else if (s[i] == ')') {
                if (!stack.empty()) stack.pop_back();
                else s[i] = '*';
            }
        }
        while (!stack.empty()) {
            s[stack.back()] = '*';
            stack.pop_back();
        }
        string res;
        for (char c : s) {
            if (c != '*') res += c;
        }
        return res;
    }
};
      

class Solution {
    public String minRemoveToMakeValid(String s) {
        StringBuilder sb = new StringBuilder(s);
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) == '(') {
                stack.push(i);
            } else if (sb.charAt(i) == ')') {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    sb.setCharAt(i, '*');
                }
            }
        }
        while (!stack.isEmpty()) {
            sb.setCharAt(stack.pop(), '*');
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) != '*') {
                res.append(sb.charAt(i));
            }
        }
        return res.toString();
    }
}
      

var minRemoveToMakeValid = function(s) {
    let arr = s.split('');
    let stack = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === '(') {
            stack.push(i);
        } else if (arr[i] === ')') {
            if (stack.length) {
                stack.pop();
            } else {
                arr[i] = '';
            }
        }
    }
    while (stack.length) {
        arr[stack.pop()] = '';
    }
    return arr.join('');
};
      

Problem Description

Given a string s containing lowercase letters and parentheses '(' and ')', your task is to remove the minimum number of parentheses so that the resulting string is a valid parentheses string. A string is considered valid if all opening parentheses have a corresponding closing parenthesis and all closing parentheses have a corresponding opening parenthesis, and the parentheses are properly nested.

• You may return any valid result after removing the minimum number of parentheses.
• Do not remove or change any lowercase letters.
• The length of s can be up to 10⁵.

For example, given s = "a)b(c)d", the output could be "ab(c)d".

Thought Process

The core challenge is to ensure that every opening parenthesis '(' has a matching closing parenthesis ')', and vice versa. If we encounter an unmatched parenthesis, we need to remove it.

A brute-force approach would try removing every possible parenthesis and checking if the string is valid, but this is extremely inefficient, especially for large strings.

Instead, we can use a stack to keep track of the positions of unmatched parentheses as we scan the string. When we find a closing parenthesis without a matching opening one, we mark it for removal. Similarly, after scanning, any unmatched opening parentheses left in the stack should also be removed.

This stack-based approach is efficient and avoids unnecessary work, making it suitable for large inputs.

Solution Approach

• Step 1: Convert the input string s into a mutable array (or StringBuilder in Java) to allow in-place modifications.
• Step 2: Initialize an empty stack to store the indices of unmatched opening parentheses '('.
• Step 3: Iterate through the string:
  • If the current character is '(', push its index onto the stack.
  • If it is ')':
    • If there is a matching '(' in the stack, pop from the stack (they match).
    • If not, mark this ')' for removal (e.g., set it to an empty character or a placeholder).
  • If it is a letter, do nothing.
• Step 4: After the loop, any indices left in the stack correspond to unmatched '('; mark those for removal as well.
• Step 5: Build the result string by skipping all marked characters.

We use a stack because it efficiently keeps track of unmatched opening parentheses, and marking characters for removal allows us to construct the final valid string in one pass.

Example Walkthrough

Let's take s = "lee(t(c)o)de)" as an example.

1. Iterate through each character:
   • 'l', 'e', 'e': letters, skip.
   • '(': push index 3 to stack.
   • 't': letter, skip.
   • '(': push index 5 to stack.
   • 'c': letter, skip.
   • ')': stack not empty (has 5), pop 5.
   • 'o': letter, skip.
   • ')': stack not empty (has 3), pop 3.
   • 'd', 'e': letters, skip.
   • ')': stack is empty, mark index 11 for removal.
2. After iteration, stack is empty (all opening parentheses matched except the last ')').
3. Build result by skipping character at index 11: "lee(t(c)o)de"

The result is a valid string with the minimum number of removed parentheses.

Time and Space Complexity

• Brute-force Approach:
  • Would involve generating all possible combinations by removing parentheses and checking validity, leading to exponential time complexity: O(2ⁿ).
• Optimized Stack Approach:
  • Time Complexity: O(n), where n is the length of s. We iterate over the string at most twice (once for marking, once for building the result).
  • Space Complexity: O(n), mainly for the stack in the worst case (all opening parentheses), and for the result string.

The optimized solution is efficient and suitable for large input sizes.

Summary

To make a parentheses string valid with the minimal number of removals, we use a stack to efficiently track unmatched opening parentheses and mark unmatched closing parentheses for removal as we scan the string. This approach ensures a linear time solution, avoids unnecessary computation, and leverages the properties of stacks for matching pairs. The final result is built by skipping all invalid parentheses, yielding a valid string with minimal edits.