Mimimum REmove to make Valid Parenthesis [FB Interview Question]

1249.Minimum Remove to Make Valid Parentheses

String

Stack

Hash Table

Problem Statement:

Given a string s of '(' , ')' and lowercase English characters, remove the minimum number of parentheses to make the string valid. Return any valid string.

Example:

Input:

s = "lee(t(c)o)de)"

→

Output:

"lee(t(c)o)de"

Algorithm:

1. Use stack to track indices of opening parentheses
2. Track indices of unmatched parentheses
3. Remove remaining opening parentheses
4. Build result string without invalid indices

Complexity:

Time: O(n) | Space: O(n)

Java Solution:

// IMPORTANT: Simpler than removeInvalidParenthesis which requires ALL possible results
public String minRemoveToMakeValid(String s) {
    Set<Integer> indexesToRemove = new HashSet<>();
    Stack<Integer> stack = new Stack<>();

    // First pass: find unmatched parentheses
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') 
            stack.push(i);  // Save index of opening parenthesis
        else if (s.charAt(i) == ')') 
            if (stack.isEmpty()) indexesToRemove.add(i);  // Unmatched closing
            else stack.pop();  // Matched pair
    }
    
    // Add remaining unmatched opening parentheses
    while (!stack.isEmpty()) indexesToRemove.add(stack.pop());
    
    // Build result string excluding invalid indices
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if (!indexesToRemove.contains(i)) 
            sb.append(s.charAt(i));
    }
    
    return sb.toString();
}

Python Solution:

def minRemoveToMakeValid(self, s: str) -> str:
    indexes_to_remove = set()
    stack = []
    
    # Find indexes of unmatched parentheses
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)
        elif char == ')':
            if not stack:
                indexes_to_remove.add(i)
            else:
                stack.pop()
                
    # Add remaining opening parentheses
    indexes_to_remove.update(stack)
    
    # Build result string
    return ''.join(c for i, c in enumerate(s) 
                  if i not in indexes_to_remove)

C++ Solution:

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        unordered_set<int> indexes_to_remove;
        stack<int> stack;
        
        // Find unmatched parentheses
        for(int i = 0; i < s.length(); i++) {
            if(s[i] == '(') {
                stack.push(i);
            }
            else if(s[i] == ')') {
                if(stack.empty()) {
                    indexes_to_remove.insert(i);
                } else {
                    stack.pop();
                }
            }
        }
        
        // Add remaining opening parentheses
        while(!stack.empty()) {
            indexes_to_remove.insert(stack.top());
            stack.pop();
        }
        
        // Build result string
        string result;
        for(int i = 0; i < s.length(); i++) {
            if(indexes_to_remove.find(i) == indexes_to_remove.end()) {
                result += s[i];
            }
        }
        
        return result;
    }
};