[Medium] 1249. Minimum Remove to Make Valid Parentheses

Difficulty: Medium
Category: String, Stack
Companies: Amazon, Facebook, Microsoft, Google

Given a string s of '(', ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

Examples

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

Constraints

• 1 <= s.length <= 10^5
• s[i] is either '(', ')', or lowercase English letter.

Solution Approaches

Approach 1: Stack-Based Validation (Recommended)

Key Insight: Use a stack to track unmatched parentheses and remove them from the string.

Algorithm:

1. Use stack to track indices of unmatched parentheses
2. For each character, push '(' indices and pop for matching ')'
3. Remove all indices remaining in stack (unmatched parentheses)
4. Return the modified string

Time Complexity: O(n)
Space Complexity: O(n)

// import java.util.*;
class Solution {
        public String minRemoveToMakeValid(String s) {
        Deque<Integer> stk = new ArrayDeque<>();
        for(int idx = 0; idx < (int)s.size(); idx++) {
            if(s.charAt(idx) == '(') stk.offer(idx);
            if(s.charAt(idx) == ')') {
                if(!stk.isEmpty() && s[stk.peek()] == '(') {
                    stk.poll();
                } else {
                    stk.offer(idx);
                }
            }
        }
        String rtn = s;
        while(!stk.isEmpty()) {
            rtn.remove(stk.peek(), 1);
            stk.poll();
        }
        return rtn;
    }
}

Solution Explanation

Approach: Parentheses matching (this problem)

Key idea: Difficulty:** Medium

How the code works: Difficulty: Medium Category: String, Stack

• Stack matches nested or LIFO structure (parentheses, monotonic scans).
• Push on open / larger; pop when the current element resolves pending work.
• Monotonic stack finds next greater/smaller in O(n).

Walkthrough — input s = "lee(t(c)o)de)", expected output "lee(t(c)o)de":

“lee(t(co)de)” , “lee(t(c)ode)” would also be accepted.

Implementation Details

Stack-Based Approach

class Solution {
        public String minRemoveToMakeValid(String s) {
        // First pass: remove unmatched ')'
        String result = "";
        int balance = 0;
        for (char c : s.toCharArray()) {
            if(c == '(') {
                balance++;
                result += c;
            } else if(c == ')') {
                if(balance > 0) {
                    balance--;
                    result += c;
                }
                // Skip unmatched ')'
            } else {
                result += c;
            }
        }

        // Second pass: remove unmatched '('
        String final_result = "";
        balance = 0;
        for(int i = result.length() - 1; i >= 0; i--) {
            char c = result[i];
            if(c == ')') {
                balance++;
                final_result = c + final_result;
            } else if(c == '(') {
                if(balance > 0) {
                    balance--;
                    final_result = c + final_result;
                }
                // Skip unmatched '('
            } else {
                final_result = c + final_result;
            }
        }

        return final_result;
    }
}

String Modification

// import java.util.*;
class Solution {
        public String minRemoveToMakeValid(String s) {
        HashSet<Integer> to_remove = new HashSet<Integer>();
        Deque<Integer> stk = new ArrayDeque<>();

        // Find unmatched parentheses for = new parentheses(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                stk.offer(i);
            } else if(s.charAt(i) == ')') {
                if(stk.length == 0) {
                    to_remove.add(i);
                } else {
                    stk.poll();
                }
            }
        }

        // Add remaining unmatched '(' to removal set
        while(!stk.isEmpty()) {
            to_remove.add(stk.peek());
            stk.poll();
        }

        // Build result String
        String result = "";
        for(int i = 0; i < s.length(); i++) {
            if(to_remove.find(i) == to_remove.iterator()) {
                result += s.charAt(i);
            }
        }

        return result;
    }
}

Edge Cases

1. Empty String: "" → ""
2. No Parentheses: "abc" → "abc"
3. All Unmatched: "))((" → ""
4. Nested Valid: "(a(b)c)" → "(a(b)c)"
5. Mixed Characters: "a)b(c)d" → "ab(c)d"

Follow-up Questions

• What if you needed to return all possible valid strings?
• How would you handle multiple types of brackets?
• What if you needed to minimize the number of removals?
• How would you optimize for very large strings?

Common Mistakes

• Skipping edge cases (empty input, single element, boundaries).
• Off-by-one errors in loops and index ranges.
• Forgetting to handle the case when no valid answer exists.

Related Problems

• LC 20: Valid Parentheses
• LC 22: Generate Parentheses
• LC 301: Remove Invalid Parentheses

Optimization Techniques

1. Stack Index Tracking: Store indices instead of characters
2. Single Pass: Use stack to identify all unmatched parentheses
3. String Building: Avoid multiple string modifications
4. Memory Efficiency: Use minimal extra space

Code Quality Notes

1. Readability: Stack approach is most intuitive
2. Performance: All approaches have O(n) time complexity
3. Space Efficiency: O(n) space for stack/set storage
4. Robustness: Handles all edge cases correctly

Key Takeaways

• Pattern: Parentheses matching (this problem)
• Difficulty:** Medium
• Category:** String, Stack

References

• LC 1249: Minimum Remove to Make Valid Parentheses on LeetCode
• LeetCode Discuss — LC 1249: Minimum Remove to Make Valid Parentheses
• LeetCode Editorial (may require premium)

Template Reference

• String Processing

Thinking Process

Difficulty: Medium

Category: String, Stack

• Stack matches nested or LIFO structure (parentheses, monotonic scans).
• Push on open / larger; pop when the current element resolves pending work.
• Monotonic stack finds next greater/smaller in O(n).

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Monotonic stack	O(n)	O(n)	Next greater/smaller element
Parentheses matching (this problem)	O(n)	O(n)	Push open, pop on close
Expression evaluation	O(n)	O(n)	Operand + operator stacks
Stack simulation	O(n)	O(n)	Process in LIFO order