Minimum Remove to make Valid Parentheses

Medium

Company Tags

You are given a string s consisting of lowercase English characters, as well as opening and closing parentheses, ( and ).

Your task is to remove the minimum number of parentheses so that the resulting string is valid.

Return the resulting string after removing the invalid parentheses.

A parentheses string is valid if all of the following conditions are met:

  1. It is the empty string, contains only lowercase characters, or
  2. It can be written as AB (A concatenated with B), where A and B are valid strings, or
  3. It can be written as (A), where A is a valid string.

Example 1:

Input: s = "nee(t(c)o)de)"

Output: "nee(t(c)ode)"

Explanation: "nee(t(co)de)" , "nee(t(c)o)de" would also be accepted.

Example 2:

Input: s = "x(y)z("

Output: "x(y)z"

Example 3:

Input: s = "))()(("

Output: "()"

Constraints:

  • 1 <= s.length <= 100,000.
  • s is made up of lowercase English characters and parentheses ().


Company Tags

Please upgrade to NeetCode Pro to view company tags.

s =