LeetCode Entry

32. Longest Valid Parentheses

03.10.2026 hard 2026 kotlin rust

Longest valid substring

32. Longest Valid Parentheses hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1501

Problem TLDR

Longest valid substring

Intuition

Put into stack:

• the lengths
• or the left wall of the substring then pop on closing braces and compare to max

Approach

• for the length: extra step to merge siblings together
• for the walls: if unbalanced - add current index as a wall

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun longestValidParentheses(s: String) = ArrayDeque(setOf(-1)).run{
        s.indices.maxOfOrNull { i ->
            if (s[i] == '(') add(i) else removeLast(); if (size<1) add(i)
            i - last()
        } ?: 0
    }

    pub fn longest_valid_parentheses(s: String) -> i32 {
        let mut v = vec![-1];
        s.bytes().zip(0..).map(|(b, i)| {
            if b == b'(' { v.push(i) } else { v.pop(); }
            if v.is_empty() { v.push(i) }; i - v.last().unwrap()
        }).max().unwrap_or(0)
    }