Is Minimum Remove to Make Valid Parentheses easy or hard?

The problem is rated Medium because it combines string processing with stack logic. The algorithm itself is linear, but handling invalid indices and reconstructing the string correctly requires careful implementation.

Minimum Remove to Make Valid Parentheses Python/Java solution

Python and Java implementations typically follow the stack approach. Iterate through the string, push indices of '(' onto the stack, and track unmatched ')'. After the pass, remove all invalid indices and rebuild the string. Both languages achieve O(n) time and O(n) space complexity.

How to solve Minimum Remove to Make Valid Parentheses in O(n)?

Traverse the string while tracking unmatched parentheses. With the stack method, push indices of '(' and remove invalid ')'. After traversal, remove any remaining indices stored in the stack. Another O(n) approach performs two passes: first remove extra closing parentheses, then remove extra opening ones.

What is the best approach for Minimum Remove to Make Valid Parentheses?

The most common solution uses a stack to track indices of unmatched parentheses while scanning the string once. Each '(' index is pushed onto the stack, and matching ')' pops it. Any remaining indices represent invalid characters that should be removed. This method runs in O(n) time with O(n) space.

Is Minimum Remove to Make Valid Parentheses asked at Google/Amazon/Meta?

Parentheses validation and expression-cleaning problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include Valid Parentheses, Remove Invalid Parentheses, and Minimum Remove to Make Valid Parentheses, all testing stack usage and string traversal skills.

What data structure is used in Minimum Remove to Make Valid Parentheses?

A stack is the primary data structure because it naturally models nested parentheses. It stores indices of opening brackets and allows constant-time matching when a closing bracket appears. Some solutions also use arrays or sets to mark invalid indices before rebuilding the string.

What is the time complexity of Minimum Remove to Make Valid Parentheses?

Optimal solutions run in O(n) time because the string is processed with a single or double linear scan. Each character is visited at most twice. Space complexity is O(n) when storing indices of invalid parentheses or building the result string.

Description Hints 2 Solution Video 14:43

1249. Minimum Remove to Make Valid Parentheses

Medium71.3% acceptance11 companies

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 <= 10⁵
s[i] is either '(' , ')', or lowercase English letter.

Asked at 11 companies

Meta Ge Digital Bloomberg Walmart Labs Snapchat Tiktok Oracle

Google Amazon Microsoft Apple

Topics

Stack String

Hints open one at a time

Hint 1

Each prefix of a balanced parentheses has a number of open parentheses greater or equal than closed parentheses, similar idea with each suffix.

Hint 2

Check the array from left to right, remove characters that do not meet the property mentioned above, same idea in backward way.

14:43

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution