1249. Minimum Remove to Make Valid Parentheses

[mah-shamim]

Discussed in #261

^{Originally posted by mah-shamim August 9, 2024}
Topics: String, Stack

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.

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.
2. Check the array from left to right, remove characters that do not meet the property mentioned above, same idea in backward way.

[mah-shamim]

The task is to remove the minimum number of parentheses from a given string to make it a valid parentheses string. A valid parentheses string is defined as:

• It is empty or contains only lowercase letters.
• It can be written as AB, where A and B are valid parentheses strings.
• It can be written as (A), where A is a valid parentheses string.

Key Points

1. Valid Parentheses String: The number of opening and closing parentheses must match. Each opening parenthesis ( must have a corresponding closing parenthesis ) in a valid order.
2. Strategy: We need to remove the invalid parentheses while keeping the valid characters (both letters and valid parentheses) in the resulting string.
3. Two-pass Approach: The solution involves two passes through the string:
   • First pass: Remove invalid closing parentheses ) that don't have a matching opening parenthesis (.
   • Second pass: Remove invalid opening parentheses ( that don't have a matching closing parenthesis ).

Approach

1. First Pass: Iterate over the string from left to right. Use a counter (openCount) to keep track of the balance between opening and closing parentheses.

   • If we encounter a ) and the counter openCount is zero, it means there is no preceding ( to balance it, so skip this ).
   • For each (, increase the counter, and for each valid ), decrease the counter.
   • Save all valid characters in a temporary stack.

2. Second Pass: After the first pass, iterate over the temporary stack in reverse. Use a counter to track the number of ) characters.

   • If we encounter an ( and the counter for ) is zero, it means there is no closing parenthesis to balance it, so skip this (.
   • Save all valid characters in the final result list.

3. Return the Result: The result list will be in reverse order, so reverse it back and return as a string.

Plan

1. Step 1: Traverse the string from left to right to filter out unnecessary closing parentheses.
2. Step 2: Traverse the filtered string from right to left to filter out unnecessary opening parentheses.
3. Step 3: Reverse the final list of valid characters and join them into a string.

Let's implement this solution in PHP: 1249. Minimum Remove to Make Valid Parentheses

<?php
/**
 * @param String $s
 * @return String
 */
function minRemoveToMakeValid(string $s): string
{
    // Stack to keep track of characters that lead to a valid string
    $stack = [];

    // Counter to track the balance of parentheses
    $openCount = 0;

    // First pass to remove invalid closing parentheses
    for ($i = 0; $i < strlen($s); $i++) {
        $char = $s[$i];
        // If a closing parenthesis is encountered with no matching open, skip it
        if ($char == ')' && $openCount == 0) {
            continue;
        }
        // If an opening parenthesis is found, increment the open count
        if ($char == '(') {
            $openCount++;
        } // If a closing parenthesis is found and there is a matching open, decrement the open count
        elseif ($char == ')') {
            $openCount--;
        }
        // Add the character to the stack as it's part of valid substring so far
        $stack[] = $char;
    }

    // Reset the open counter for the second pass
    $openCount = 0;
    // List to store the characters for the final answer
    $answer = [];

    // Second pass to remove invalid opening parentheses; process characters in reverse
    for ($i = count($stack) - 1; $i >= 0; $i--) {
        $char = $stack[$i];
        // If an opening parenthesis is encountered with no matching close, skip it
        if ($char == '(' && $openCount == 0) {
            continue;
        }
        // If a closing parenthesis is found, increment the open count
        if ($char == ')') {
            $openCount++;
        } // If an opening parenthesis is found and there is a matching close, decrement the open count
        elseif ($char == '(') {
            $openCount--;
        }
        // Add the character to the answer as it is part of a valid substring
        $answer[] = $char;
    }

    // The characters in answer are in reverse order, reverse them back to the correct order
    return implode('', array_reverse($answer));
}

// Example usage:
$s1 = "lee(t(c)o)de)";
$s2 = "a)b(c)d";
$s3 = "))((";

echo minRemoveToMakeValid($s1) . "\n"; // Output: "lee(t(c)o)de"
echo minRemoveToMakeValid($s2) . "\n"; // Output: "ab(c)d"
echo minRemoveToMakeValid($s3) . "\n"; // Output: ""
?>

Explanation:

The algorithm uses two passes to ensure that only valid parentheses are kept:

• First pass ensures that we remove invalid closing parentheses ) which don’t have matching opening parentheses (.
• Second pass ensures that we remove invalid opening parentheses ( which don’t have matching closing parentheses ).

Each pass modifies the string based on the matching parentheses, making sure the final string is valid.

Example Walkthrough

Example 1:

Input: "lee(t(c)o)de)"
First pass (remove invalid closing parentheses):
Result after first pass: "lee(t(c)o)de"
Second pass (remove invalid opening parentheses):
Final result: "lee(t(c)o)de"

Example 2:

Input: "a)b(c)d"
First pass (remove invalid closing parentheses):
Result after first pass: "ab(c)d"
Second pass (no change needed as all parentheses are valid):
Final result: "ab(c)d"

Example 3:

Input: "))(("
First pass (remove invalid closing parentheses):
Result after first pass: ""
Second pass (no change needed as there are no valid parentheses):
Final result: ""

Time Complexity

• Time Complexity: O(n), where n is the length of the input string.
  • We traverse the string twice, each traversal taking O(n) time.
• Space Complexity: O(n), where n is the length of the input string.
  • We use a temporary stack to store intermediate results, which could store up to the length of the input.

This approach ensures that we can efficiently remove invalid parentheses in a two-pass solution. By using a stack and maintaining a balance between opening and closing parentheses, we can guarantee a valid output string with minimal removals. The solution is both time-efficient and space-efficient, handling large input sizes within the problem's constraints.