DSA problem
Minimum Remove to Make Valid Parentheses
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 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.
A two-pass O(n) approach (count opens and closes) works but is awkward to reason about. The cleanest formulation is the stack approach: scan the string keeping a stack of indices of unmatched '(' characters. When you see a ')', if the stack has an unmatched '(', pop it (a valid pair is formed); if it does not, mark this ')' as a "to remove" position.
After the scan, any indices left in the stack are unmatched '(' that must also be removed. Collect all such indices into a set, then rebuild the string by emitting every character whose index is not marked. This is O(n) time and O(n) extra space, and naturally produces one valid answer with the minimum number of removals.
Examples
s = "lee(t(c)o)de)""lee(t(c)o)de"s = "a)b(c)d""ab(c)d"s = "))(("""Constraints
- 1 <= s.length <= 10^5
- s[i] is either '(' , ')', or lowercase English letter.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.