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
- It can be written as
AB(Aconcatenated withB), whereAandBare valid strings, or - It can be written as
(A), whereAis a valid string.
Example 1
Input
s = "lee(t(c)o)de)"Output
"lee(t(c)o)de""lee(t(co)de)" and "lee(t(c)ode)" would also be accepted.
Example 2
Input
s = "a)b(c)d"Output
"ab(c)d"Removing the unmatched closing parenthesis after
a gives a valid string.Constraints
- 1 <= s.length <= 10^5
- s[i] is either '(' , ')', or lowercase English letter.
Asked at 11 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.