8.1 Longest Valid Parentheses

8.1.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 32
• Difficulty: Hard
• URL: https://leetcode.com/problems/lc-longest-valid-parentheses/
• Tags:
• Techniques: Dynamic Programming, Stack

8.1.2 Description

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

8.1.3 Examples

Input: s = " )()() "
Output: 4

8.1.4 Constraints

• 0 <= s.length <= 3 * 10^4

8.1.5 Solution - Stack

8.1.5.1 Walkthrough

Maintain a stack of indices. Push -1 as a sentinel. For each character: - When '(', push its index. - When ')', pop the stack. If it becomes empty, push the current index (new base). Otherwise update the answer with i - stack.peek().

8.1.5.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

8.1.5.3 Implementation Steps

1. Initialize stack with -1 and maxLen = 0.
2. For each index i:
   • If s[i] == '(', push i.
   • Else pop; if stack empty push i, else maxLen = max(maxLen, i - stack.peek()).
3. Return maxLen.

8.1.5.4 Code - Java

public int longestValidParentheses(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);
    int longest = 0;

    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                longest = Math.max(longest, i - stack.peek());
            }
        }
    }

    return longest;
}