Minimum Remove Valid Parentheses

Remove the minimum number of parentheses to make the string valid.

strings stack validation parentheses

Given a string s that may contain letters, '(' and ')', return the smallest possible string after removing the minimum number of parentheses so that every open parenthesis '(' is matched with a closing parenthesis ')' in the correct order. The resulting string should contain only balanced parentheses and the original letters in their original order. If there are multiple valid results with the same minimal removals, any one is acceptable, but your solution will be tested against a deterministic expected result (see examples). Your task is to implement the function `min_remove_to_make_valid(s: str) -> str`.

Constraints

1 <= len(s) <= 10^5. s consists of lowercase English letters and parentheses '(' and ')'. The solution should run in O(n) time and O(n) auxiliary space.

Example

>>> min_remove_to_make_valid('leet(tc)ode')
'leet(tc)ode'
>>> min_remove_to_make_valid('a)b(c)d')
'ab(c)d'
>>> min_remove_to_make_valid('))((')
''
>>> min_remove_to_make_valid('(a(b(c)d)')
'a(b(c)d)'

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Track indices of unmatched opening parentheses in a stack.

When you encounter a closing parenthesis and the stack is empty, mark that closing index for removal.

After the scan, all indices still on the stack are unmatched openings; remove them too.

Build the result by skipping all marked indices.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.