Code Logo

Longest Valid Parentheses

Published at23 Jul 2026
Created by
Hard 0 views
Like0

You are given a string containing only ( and ). Find the length of the longest valid (well-formed) parentheses substring. A substring is valid if every opening parenthesis has a matching closing parenthesis in the correct order.

A stack-based approach with a sentinel index solves this efficiently. Push -1 onto the stack as a base. When you encounter (, push its index. When you encounter ), pop the top. If the stack becomes empty after popping, push the current index as the new base. Otherwise, the current valid length is current_index - stack.peek(). Track the maximum length seen.

For example, "(()" → the substring "()" starting at index 1 has length 2. ")()())" → the substring "()()" has length 4.

The sentinel index -1 on the stack is the key trick. It serves as a base for calculating valid substring lengths. When a closing bracket matches with an opening bracket at some earlier position, the valid length is the distance from that opening bracket's match to the current position.

When a closing bracket is encountered and the stack becomes empty after popping, it means this closing bracket has no matching opening bracket. This bracket becomes a separator, and its index is pushed as the new base for future calculations.

Algorithm overview: Push -1 initially. For '(' push its index. For ')', pop the top. If the stack becomes empty, push the current index as new base. Otherwise, calculate length as current index minus top of stack, and update the maximum.

This problem is harder than simple bracket matching because it asks for the longest contiguous substring, not just whether the entire string is valid. The sentinel value is a widely applicable technique.

This problem is harder than simple bracket matching because it asks for the longest contiguous valid substring, not just whether the entire string is valid. The stack must track positions, not just brackets. The sentinel value technique is widely applicable in substring problems where you need a reference point before the start of the string.

Practice tracing through examples like "()(()" where the longest valid substring is "()" at positions 0-1 or 2-3 (length 2). The sentinel at -1 ensures the first valid pair is correctly measured.

Example Input & Output

Example 1
Input
(()
Output
2
Explanation

The longest valid substring is '()' at indices 1-2 with length 2.

Example 2
Input
Output
0
Explanation

Empty string has no valid parentheses.

Example 3
Input
())()())
Output
4
Explanation

The longest valid substring is '()()' from index 3-6 with length 4.

Algorithm Flow

Recommendation Algorithm Flow for Longest Valid Parentheses
Recommendation Algorithm Flow for Longest Valid Parentheses

Solution Approach

Push -1 onto the stack. Iterate through each character. If it's (, push its index. If it's ), pop the top. If the stack is empty after popping, push the current index as the new base. Otherwise, calculate i - stack.peek() and update the maximum length.

function solution(s) {
  var stack = [-1];
  var maxLen = 0;
  for (var i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push(i);
    } else {
      stack.pop();
      if (stack.length === 0) {
        stack.push(i);
      } else {
        maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
      }
    }
  }
  return maxLen;
}

Time complexity is O(n). Space complexity is O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int solution(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;
    }
}