Course4all
Join us on telegram
Home/dsa/Dynamic Programming/Longest Valid Parentheses

Longest Valid Parentheses

Master this topic with zero to advance depth.

Longest Valid Parentheses

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

Visual Representation

s = ")()())" Substrings: () -> 2 ()() -> 4 (Max) DP Strategy: dp[i] = length of longest valid parentheses ending at index i.
Hard

Examples

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

The longest valid parentheses substring is "()".

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

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

Approach 1

Level I: Dynamic Programming

Intuition

We use a 1D DP array where dp[i] is the length of the longest valid parentheses ending at index i.

Thought Process

  1. If s[i] == '(', dp[i] = 0 (valid substring can't end with open paren).
  2. If s[i] == ')':
    • If s[i-1] == '(', then dp[i] = dp[i-2] + 2.
    • If s[i-1] == ')' and s[i - dp[i-1] - 1] == '(', then dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2.
  3. Keep track of maximum dp[i].
⏱ O(N)💾 O(N)

Detailed Dry Run

s = "()()"

icharCalculationdp[i]
0(-0
1)dp[0-1]+2 = 22
2(-0
3)dp[3-2]+2 = dp[1]+2 = 44
java
public class Main {
    public static 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) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses(")()())")); // 4
    }
}
Approach 2

Level II: Stack-Based Approach

Intuition

Use a stack to track unmatched parenthesis indices. Whenever we find a matching pair, the valid length is i - stack.peek().

Visual

s = ")()())" stack: [-1] i=0 ')': stack = [] -> push 0? No, stack is empty -> push i=0 i=1 '(': stack = [0, 1] i=2 ')': pop 1 -> stack = [0], len = 2-0=2 i=3 '(': stack = [0, 3] i=4 ')': pop 3 -> stack = [0], len = 4-0=4 i=5 ')': pop 0 -> stack = [], push 5 Max = 4
⏱ O(N)💾 O(N)

Detailed Dry Run

s="())". stack=[-1]. i=0 '(': push 0. i=1 ')': pop 0, len=1-(-1)=2, max=2. i=2 ')': pop -1, empty -> push 2. Result = 2.

java
import java.util.*;

public class Main {
    public static 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;
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses(")()()")); // 4
    }
}

⚠️ Common Pitfalls & Tips

Initialize the stack with -1 as a sentinel base index. Without this, first close parenthesis would fail to compute length (0 - nothing = invalid).

Approach 3

Level III: Two Counters (Optimal Space)

Intuition

We can optimize space to O(1) by scanning the string twice (left-to-right and right-to-left) while keeping track of left and right parentheses counts.

Logic Steps

  1. Scan Left to Right:
    • left++ for '(', right++ for ')'.
    • If left == right, current length is 2 * left. Update max.
    • If right > left, reset both to 0.
  2. Scan Right to Left:
    • Repeat same logic but reset if left > right.
⏱ O(N)💾 O(1)

Detailed Dry Run

s = "(()"

  1. L-R: '('(L1,R0), '('(L2,R0), ')'(L2,R1). L!=R. Max=0.
  2. R-L: ')'(L0,R1), '('(L1,R1) -> Max=2, '('(L2,R1) -> Reset. Result: 2.
java
public class Main {
    public static int longestValidParentheses(String s) {
        int left = 0, right = 0, maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') left++; else right++;
            if (left == right) maxLen = Math.max(maxLen, 2 * right);
            else if (right > left) { left = 0; right = 0; }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') left++; else right++;
            if (left == right) maxLen = Math.max(maxLen, 2 * left);
            else if (left > right) { left = 0; right = 0; }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestValidParentheses("(()")); // 2
    }
}
← Previous QuestionBurst Balloons
Next Question →Edit Distance