Algorithm Day91 - Longest Valid Parentheses

Posted on In , , Views:

🧩 Problem Description

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

💬 Examples

Example 1

1
2
3
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2

1
2
3
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3

1
2
Input: s = ""
Output: 0

💡 Intuition

We want the longest substring that forms valid parentheses. Three common approaches:

  1. Stack approach: Track indices of unmatched parentheses.
  2. Dynamic Programming: Use dp[i] to store the length of longest valid substring ending at i.
  3. Two-pass scanning: Left-to-right and right-to-left counters for balance.

🔢 Java Code (Stack Approach)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxLen = 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 {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }
}

🔢 Java Code (DP Approach)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] dp = new int[n];
        int maxLen = 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }
}

⏱ Complexity Analysis

  • Stack approach:

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

  • DP approach:

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

  • Two-pass scanning:

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

✍️ Summary

  • Multiple methods exist: stack, DP, or two-pass counting.
  • Stack is intuitive and straightforward.
  • DP gives structured state-based reasoning.
  • Two-pass is space-optimized.

Related problems: lc-20 (Valid Parentheses), lc-22 (Generate Parentheses), lc-301 (Remove Invalid Parentheses).