Longest valid parentheses

String Dynamic Programming Stack

38.1% acceptance

Jan 12, 2026

13253

464

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

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_valid_parentheses(s: String) -> i32 {
    let mut max_len = 0;
    let mut stack: Vec<i32> = vec![-1];
    
    for (i, ch) in s.chars().enumerate() {
      if ch == '(' {
        stack.push(i as i32);
      } else {
        stack.pop();
        if stack.is_empty() {
          stack.push(i as i32);
        } else {
          max_len = max_len.max(i as i32 - stack[stack.len() - 1]);
        }
      }
    }
    
    max_len
  }
}