Complexity Analysis: The number of subsequences for a string of length $N$ is $2^N$. Checking validity takes $O(N)$. The total time complexity is roughly $O(N \cdot 2^N)$.

Why it fails: With constraints where s.length can be up to $10^5$, an exponential solution is impossible. This approach will immediately result in a Time Limit Exceeded (TLE) error. We need a linear time solution.

Core Insight for Minimum Remove to Make Valid Parentheses

The core insight for the optimal solution is realizing that we only need to remove a parenthesis if it violates the validity rules immediately or remains unresolved at the end of the string.

We can define invalidity in two specific ways:

1. Invalid Closing Parenthesis ): A closing parenthesis is invalid if there is no preceding unmatched opening parenthesis available to pair with it.
2. Invalid Opening Parenthesis (: An opening parenthesis is invalid if, after scanning the entire string, it was never closed by a subsequent ).

The Stack - Valid Parentheses Matching pattern allows us to enforce this logic in a single pass (or two passes depending on implementation).

Visual Description: Imagine scanning the string from left to right. We maintain a stack of indices.

• When we encounter (, we push its index onto the stack. This signifies an open bracket waiting for a match.
• When we encounter ), we check the stack:
  • If the stack is not empty, we pop the top index. This means the current ) has successfully matched with the ( at the popped index.
  • If the stack is empty, this ) has no match. We mark this specific index for removal.
• After the scan is complete, any indices remaining in the stack represent ( characters that were never closed. These must also be marked for removal.

By storing indices rather than characters, we gain the ability to pinpoint exactly which characters to delete from the original string.

Execution Flow

Let's trace s = "a)b(c)d".

1. i = 0, char = 'a': Ignored.
2. i = 1, char = ')': Stack is empty. This ) is invalid. Mark index 1 for removal.
3. i = 2, char = 'b': Ignored.
4. i = 3, char = '(': Push index 3 to stack. Stack: [3].
5. i = 4, char = 'c': Ignored.
6. i = 5, char = ')': Stack is not empty ([3]). Match found. Pop 3. Stack: [].
7. i = 6, char = 'd': Ignored.
8. End Loop: Stack is empty, so no excess (.
9. Reconstruction: Indices to remove: {1}.
   • Keep 0 ('a')
   • Skip 1 (')')
   • Keep 2 ('b')
   • Keep 3 ('(')
   • Keep 4 ('c')
   • Keep 5 (')')
   • Keep 6 ('d')
10. Result: "ab(c)d".

Proof of Correctness

The algorithm guarantees the minimum number of removals based on the definition of valid parentheses.

• A ) is only removed if there is strictly no ( available to match it at that point in the scan. Keeping it would structurally violate validity.
• A ( is only removed if there is strictly no ) available to close it after it appears. Keeping it would leave an open group.

Since we only remove characters that must be removed to satisfy the validity constraint, the number of removals is minimized, and the resulting string is valid.

Reference Implementation

C++ Solution for LeetCode 1249

cpp
#include <string>
#include <stack>
#include <vector>

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        std::stack<int> st;
        // Iterate through string to find invalid parentheses
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') {
                st.push(i);
            } else if (s[i] == ')') {
                if (!st.empty()) {
                    st.pop(); // Match found
                } else {
                    s[i] = '*'; // Mark invalid closing parenthesis
                }
            }
        }

        // Mark remaining invalid open parentheses
        while (!st.empty()) {
            s[st.top()] = '*';
            st.pop();
        }

        // Construct the result string
        std::string result = "";
        for (char c : s) {
            if (c != '*') {
                result += c;
            }
        }
        
        return result;
    }
};

Java Solution for LeetCode 1249

java
class Solution {
    public String minRemoveToMakeValid(String s) {
        StringBuilder sb = new StringBuilder(s);
        Stack<Integer> stack = new Stack<>();

        // Pass 1: Remove invalid closing parentheses and track open ones
        for (int i = 0; i < sb.length(); i++) {
            char c = sb.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else if (c == ')') {
                if (!stack.isEmpty()) {
                    stack.pop();
                } else {
                    sb.setCharAt(i, '*'); // Mark for deletion
                }
            }
        }

        // Pass 2: Mark remaining open parentheses
        while (!stack.isEmpty()) {
            sb.setCharAt(stack.pop(), '*');
        }

        // Pass 3: Build final string
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < sb.length(); i++) {
            char c = sb.charAt(i);
            if (c != '*') {
                result.append(c);
            }
        }

        return result.toString();
    }
}

Python Solution for LeetCode 1249

python
class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        s_list = list(s)
        stack = []
        
        # Pass 1: Identify invalid ')' and track '('
        for i, char in enumerate(s):
            if char == '(':
                stack.append(i)
            elif char == ')':
                if stack:
                    stack.pop()
                else:
                    s_list[i] = '' # Mark invalid ')' for deletion
        
        # Pass 2: Identify invalid '(' remaining in stack
        while stack:
            s_list[stack.pop()] = ''
            
        return "".join(s_list)

• Mistake: Using an integer counter (increment for (, decrement for )) instead of a stack of indices.
• Concept: A counter works for checking if a string is valid (LeetCode 20), but it doesn't tell you where the invalid parentheses are. If you have extra ( at the end, a counter tells you "you have 2 extra", but not which indices they occupy.
• Consequence: You cannot correctly identify which specific ( to remove to satisfy the problem requirements.