Leetcode 32. Longest Valid Parentheses

32. Longest Valid Parentheses

Hard, Dynamic Programming

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: s = "(()"

Output: 2

Explanation: The longest valid parentheses substring is "()".

Example 2:

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

Output: 4

Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""

Output: 0

 

Constraints:

• 0 <= s.length <= 3 * 10⁴

s[i] is '(', or ')'.

SOLUTION

To solve the Longest Valid Parentheses problem, we need to determine the maximum length of well-formed parentheses substrings. Here are the possible approaches:

---

Plan:

1. Stack-based Approach:

   • Use a stack to track indices of unmatched parentheses.
   • Push -1 to the stack initially to act as a base index for valid substrings.
   • Iterate through the string:
     • Push the index when encountering an opening parenthesis (.
     • When encountering a closing parenthesis ):
       • Pop the top of the stack.
       • If the stack is empty, push the current index.
       • Otherwise, calculate the valid substring length as the difference between the current index and the top of the stack.
   • Keep track of the maximum valid substring length.

2. Dynamic Programming:

   • Use a DP array dp where dp[i] represents the length of the longest valid substring ending at index i.
   • Traverse the string:
     • If s[i] is ) and the preceding character forms a valid pair (e.g., s[i-1] is ():
       • Add 2 to the value of dp[i-2] (or 0 if i-2 is out of bounds).
     • If s[i] is ) and there’s a valid substring ending before a matching (:
       • Extend the valid length by considering the substring length before the matching (.
   • Keep track of the maximum value in the dp array.

3. Two-Pointer Traversal:

   • Use two counters, left and right, to traverse the string twice:
     • From left to right, count ( and ).
       • If they are equal, calculate the length.
       • If right > left, reset the counters.
     • From right to left, count ) and (.
       • If they are equal, calculate the length.
       • If left > right, reset the counters.
   • Keep track of the maximum length.

---

Implementation (Stack-based Approach):

public class Solution {
    public int LongestValidParentheses(string s) {
        Stack<int> stack = new Stack<int>();
        stack.Push(-1); // Base index for valid substrings
        int maxLength = 0;

        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                stack.Push(i); // Push index of '('
            } else {
                stack.Pop(); // Pop for ')'
                if (stack.Count == 0) {
                    stack.Push(i); // Push current index as base
                } else {
                    maxLength = Math.Max(maxLength, i - stack.Peek());
                }
            }
        }

        return maxLength;
    }
}

---

Implementation (Dynamic Programming):

public class Solution {
    public int LongestValidParentheses(string s) {
        int n = s.Length;
        if (n == 0) return 0;

        int[] dp = new int[n];
        int maxLength = 0;

        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLength = Math.Max(maxLength, dp[i]);
            }
        }

        return maxLength;
    }
}

---

Implementation (Two-Pointer Traversal):

public class Solution {
    public int LongestValidParentheses(string s) {
        int left = 0, right = 0, maxLength = 0;

        // Left to right
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') left++;
            else right++;

            if (left == right) {
                maxLength = Math.Max(maxLength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }

        // Right to left
        left = right = 0;
        for (int i = s.Length - 1; i >= 0; i--) {
            if (s[i] == ')') right++;
            else left++;

            if (left == right) {
                maxLength = Math.Max(maxLength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }

        return maxLength;
    }
}

---

Complexity Analysis:

1. Stack-based Approach:

   • Time Complexity: $O(n)$ — Single traversal of the string.
   • Space Complexity: $O(n)$ — Stack space.

2. Dynamic Programming:

   • Time Complexity: $O(n)$ — Single traversal of the string.
   • Space Complexity: $O(n)$ — DP array.

3. Two-Pointer Traversal:

   • Time Complexity: $O(n)$ — Two traversals of the string.
   • Space Complexity: $O(1)$ — Constant space.

---

Example Outputs:

Example 1:

• Input: "(()"
• Output: 2

Example 2:

• Input: ")()())"
• Output: 4

Example 3:

• Input: ""
• Output: 0