1249. Minimum Remove to Make Valid Parentheses
Minimum Remove to Make Valid Parentheses (LeetCode 1249) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Valid Parentheses Matching subpattern.
How to solve Minimum Remove to Make Valid Parentheses
Minimum Remove to Make Valid Parentheses is a Valid Parentheses problem, part of Stack Patterns. Master parentheses validation and balancing using stack. Handle multiple bracket types and minimum additions.
Work towards the solution in these steps:
- Each prefix of a balanced parentheses has a number of open parentheses greater or equal than closed parentheses, similar idea with each suffix.
- Check the array from left to right, remove characters that do not meet the property mentioned above, same idea in backward way.
The reference solution runs in O(n) time and O(1) space.
The Minimum Remove to Make Valid Parentheses solution and editorial walks through the full approach with reference code.
Problem statement
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.
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 <= 105
- s[i] is either '(' , ')', or lowercase English letter.
Topics and companies
Topics: String, Stack.
Reported in interviews at Facebook, ByteDance, Bloomberg, Amazon, Goldman Sachs, LinkedIn, Apple.
How to practise Minimum Remove to Make Valid Parentheses on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Minimum Remove to Make Valid Parentheses in the code editor, or read the Minimum Remove to Make Valid Parentheses editorial for a worked solution with its approach and complexity analysis.
Where Minimum Remove to Make Valid Parentheses sits in the DSA pattern sheet
Problems related to Minimum Remove to Make Valid Parentheses
Other problems that use the same Valid Parentheses Matching and Stack Patterns techniques:
- Longest Valid Parentheses — Hard, same subpattern
- Minimum Add to Make Parentheses Valid — Medium, same subpattern
- Minimum Number of Swaps to Make the String Balanced — Medium, same subpattern
- Valid Parentheses — Easy, same subpattern
- Valid Parenthesis String — Medium, same subpattern
- Asteroid Collision — Medium, same pattern
Minimum Remove to Make Valid Parentheses FAQ
What is the LeetCode number of Minimum Remove to Make Valid Parentheses?
Minimum Remove to Make Valid Parentheses is LeetCode problem 1249, rated Medium.
What pattern is used to solve Minimum Remove to Make Valid Parentheses?
Minimum Remove to Make Valid Parentheses is a Valid Parentheses problem. It belongs to the Stack Patterns pattern, in the Valid Parentheses Matching subpattern.
What is the time complexity of Minimum Remove to Make Valid Parentheses?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Minimum Remove to Make Valid Parentheses?
Minimum Remove to Make Valid Parentheses has been reported in interviews at Facebook, ByteDance, Bloomberg, Amazon, Goldman Sachs, LinkedIn, Apple.