MANG Problem #11: Longest Valid Parentheses (Hard)

1. Problem Statement

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

Input: s = ")()())"
Output: 4 (The valid substring is "()()")

2. Approach: Bottom-Up DP

We want to find the longest valid string ending at each index.

State: dp[i] is the length of the longest valid parentheses ending at index i.
Base Case: dp[i] = 0 (All values initialized to 0).
Transition:
- We only care about indices where s[i] == ')'.
- Case 1: s[i] == ')' and s[i-1] == '('.
  - Found a pair ().
  - dp[i] = dp[i-2] + 2.
- Case 2: s[i] == ')' and s[i-1] == ')'.
  - If s[i - dp[i-1] - 1] == '(', then the current ) matches an opening bracket before the previous valid string.
  - dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2].

3. Java Implementation

public int longestValidParentheses(String s) {
    int maxLen = 0;
    int[] dp = new int[s.length()];
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == ')') {
            if (s.charAt(i - 1) == '(') {
                // Case 1: ...()
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                // Case 2: ...)) matching an earlier (
                dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0);
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
    }
    return maxLen;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: Parentheses are like mirrors. A closing bracket ) is only useful if it has a matching opener (.
The DP Chain: In Case 2, we are essentially saying: "The previous character was a closing bracket of a valid string of length X. If the character before that string was an opening bracket, then our current closing bracket closes a new, larger valid string."
The Stitching: Notice the + dp[...] part at the end of the formulas. This is critical—it "stitches" the current valid string to any valid string that immediately preceded it.

5. Interview Discussion

Interviewer: "What is the space complexity?"
You: "O(N) for the DP array."
Interviewer: "Can you solve it in O(1) space?"
You: "Yes! We can use two counters (left and right) and scan the string twice (left-to-right and right-to-left). Whenever the counters match, we update the max length."