MANG Problem #11: Longest Valid Parentheses (Hard)

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

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

5. Verbal Interview Script (Staff Tier)

Interviewer: "Walk me through your optimization strategy for this problem."

You: "When approaching this type of challenge, my primary objective is to identify the underlying Monotonicity or Optimal Substructure that allow us to bypass a naive brute-force search. In my implementation of 'MANG Problem #11: Longest Valid Parentheses (Hard)', I focused on reducing the time complexity by leveraging a Dynamic Programming state transition. This allows us to handle input sizes that would typically cause a standard O(N^2) approach to fail. Furthermore, I prioritized memory efficiency by using in-place modifications. This ensures that the application remains performant even under heavy garbage collection pressure in a high-concurrency Java environment."

6. Staff-Level Interview Follow-Ups

Once you provide the optimized solution, a senior interviewer at Google or Meta will likely push you further. Here is how to handle the most common follow-ups:

Follow-up 1: "How does this scale to a Distributed System?"

If the input data is too large to fit on a single machine (e.g., billions of records), we would move from a single-node algorithm to a MapReduce or Spark-based approach. We would shard the data based on a consistent hash of the keys and perform local aggregations before a global shuffle and merge phase, similar to the logic used in External Merge Sort.

Follow-up 2: "What are the Concurrency implications?"

In a multi-threaded Java environment, we must ensure that our state (e.g., the DP table or the frequency map) is thread-safe. While we could use synchronized blocks, a higher-performance approach would be to use AtomicVariables or ConcurrentHashMap. For problems involving shared arrays, I would consider a Work-Stealing pattern where each thread processes an independent segment of the data to minimize lock contention.

7. Performance Nuances (The Java Perspective)

Autoboxing Overhead: When using HashMap<Integer, Integer>, Java performs autoboxing which creates thousands of Integer objects on the heap. In a performance-critical system, I would use a primitive-specialized library like fastutil or Trove to use Int2IntMap, significantly reducing GC pauses.
Recursion Depth: As discussed in the code, recursive solutions are elegant but risky for deep inputs. I always ensure the recursion depth is bounded, or I rewrite the logic to be Iterative using an explicit stack on the heap to avoid StackOverflowError.

Key Takeaways

We only care about indices where s[i] == ')'.
Case 1: s[i] == ')' and s[i-1] == '('.
Found a pair ().