Minimum Remove to Make Valid Parentheses

Minimum Remove to Make Valid Parentheses 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.

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

• Stack Patterns pattern guide
• Valid Parentheses Matching subpattern
• The full DSA patterns sheet
• All coding practice problems

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
• Asteroid Collision — Medium, same pattern
• Basic Calculator — Hard, same pattern