Practice/Meta/Leetcode 1249. Minimum Remove to Make Valid Parentheses

Leetcode 1249. Minimum Remove to Make Valid Parentheses

CodingMust

Problem

You are given a string containing lowercase English letters along with opening and closing parentheses. Your task is to remove the minimum number of parentheses (either opening '(' or closing ')') to make the resulting string valid.

A valid parentheses string is one where:

• Every opening bracket has a corresponding closing bracket
• Brackets are properly nested (no closing bracket appears before its matching opening bracket)
• All other characters (letters) remain in their original positions

Return any valid result. If multiple solutions exist with the same minimum number of removals, any one is acceptable.

Requirements

1. Remove the minimum number of parentheses to make the string valid
2. Preserve the relative order of all remaining characters
3. Keep all lowercase letters in their original positions
4. Return a string where all parentheses are properly matched and nested

Constraints

• 1 ≤ length of string ≤ 100,000
• The string consists only of lowercase English letters, '(', and ')'
• Your solution should run in O(n) time complexity
• Aim for O(n) space complexity

Examples

Example 1:

Input: s = "ab(c)d)e(f" Output: "ab(c)def" Explanation: We remove the unmatched ')' after 'd' and the unmatched '(' before 'f'. The substring "(c)" remains properly matched.

Example 2:

Input: s = "))((" Output: "" Explanation: All brackets are unmatched. Removing all of them gives an empty string, which is valid.

Example 3:

Input: s = "((a)b(c))" Output: "((a)b(c))" Explanation: All brackets are already properly matched, so no removal is necessary.

Example 4:

Input: s = "x(y(z))" Output: "x(y(z))" Explanation: The brackets form a valid nested structure, so we keep everything.