{x}
blog image

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 (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.

Solution Explanation: Minimum Remove to Make Valid Parentheses

This problem asks us to find the minimum number of parentheses to remove from a given string to make it a valid parentheses string. A valid parentheses string is defined recursively:

  1. An empty string is valid.
  2. A string containing only lowercase characters is valid.
  3. If A and B are valid strings, then AB is valid.
  4. If A is a valid string, then (A) is valid.

The most efficient approach is a two-pass algorithm. We make one pass from left to right and another from right to left, removing invalid parentheses in each pass.

Algorithm:

Pass 1 (Left to Right):

  1. Initialize a counter open to 0.
  2. Iterate through the string:
    • If we encounter an opening parenthesis (, increment open.
    • If we encounter a closing parenthesis ):
      • If open is 0 (meaning we have more closing than opening parentheses), it's an extra closing parenthesis; remove it.
      • Otherwise, decrement open.
    • If we encounter a lowercase character, ignore it.

Pass 2 (Right to Left):

  1. Initialize a counter close to 0.
  2. Iterate through the string in reverse:
    • If we encounter a closing parenthesis ), increment close.
    • If we encounter an opening parenthesis (:
      • If close is 0 (meaning we have more opening than closing parentheses), it's an extra opening parenthesis; remove it.
      • Otherwise, decrement close.
    • If we encounter a lowercase character, ignore it.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the string. We iterate through the string twice.
  • Space Complexity: O(n) in the worst case (though in practice, it might be less). This is because we might need to store the entire string in the case of many invalid parentheses that need to be removed, or use an auxiliary stack/array of size O(n).

Code Implementations:

The code implementations below demonstrate the two-pass algorithm in various programming languages. Note that these implementations use different data structures to achieve the same goal. Some use stacks, while others build up the final string directly. The core logic remains the same.

(See the code examples in the original response)

Example Walkthrough:

Let's walk through s = "lee(t(c)o)de))":

Pass 1 (Left to Right):

  • l, e, e: ignored
  • (: open = 1
  • t: ignored
  • (: open = 2
  • c: ignored
  • ): open = 1
  • o: ignored
  • ): open = 0
  • d: ignored
  • e: ignored
  • ): open = 0 (extra closing parenthesis, removed)
  • ): open = 0 (extra closing parenthesis, removed)

After Pass 1: "lee(t(c)o)de"

Pass 2 (Right to Left):

  • ): close = 1
  • e: ignored
  • d: ignored
  • o: ignored
  • ): close = 2
  • (: close = 1
  • c: ignored
  • (: close = 0
  • t: ignored
  • (: close = 0 (extra opening parenthesis, would be removed if present from the previous pass)
  • e: ignored
  • l: ignored
  • e: ignored

The result is "lee(t(c)o)de".

This two-pass approach provides a clear, efficient, and easy-to-understand solution to the problem. Other approaches, such as using a single pass with a stack, are possible, but they tend to be slightly more complex to implement and understand.