NUHMAN.com

Introduction

LeetCode 32: Longest Valid Parentheses is a popular coding interview problem that asks you to find the length of the longest valid (well-formed) parentheses substring in a given string.

This problem can be solved efficiently using stack, two-pointers, or dynamic programming, with the stack method being one of the most intuitive.

Problem Statement

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

Examples

go

Input: s = "(()"
Output: 2
Explanation: The longest valid substring is "()"
go

Input: s = ")()())"
Output: 4
Explanation: The longest valid substring is "()()"
go

Input: s = ""
Output: 0

Approach: Stack-Based Solution

We use a stack to store indices of characters. This helps us track boundaries of valid substrings.

🔁 Steps:

1. Initialize maxLen = 0 and a stack with -1 as a base.
2. Traverse each character in the string:

• If it's '(', push its index.
• If it's ')', pop the top of the stack:
• If the stack is empty → push current index as base.
• If not → compute valid length as i - stack[top], update maxLen.

1. Return maxLen.

Go Implementation

go

func longestValidParentheses(s string) int {
    maxLen := 0
    stack := []int{-1} // base for valid substring calculation

    for i, ch := range s {
        if ch == '(' {
            stack = append(stack, i)
        } else {
            stack = stack[:len(stack)-1]
            if len(stack) == 0 {
                stack = append(stack, i)
            } else {
                length := i - stack[len(stack)-1]
                if length > maxLen {
                    maxLen = length
                }
            }
        }
    }
    return maxLen
}

Alternative Approach: Two-Pass Counter Method

You can also solve it with two counters (left-to-right and right-to-left pass):

go

func longestValidParentheses(s string) int {
    maxLen := 0
    left, right := 0, 0

    // Left to right
    for _, ch := range s {
        if ch == '(' {
            left++
        } else {
            right++
        }

        if left == right {
            maxLen = max(maxLen, 2*right)
        } else if right > left {
            left, right = 0, 0
        }
    }

    left, right = 0, 0
    // Right to left
    for i := len(s) - 1; i >= 0; i-- {
        if s[i] == '(' {
            left++
        } else {
            right++
        }

        if left == right {
            maxLen = max(maxLen, 2*left)
        } else if left > right {
            left, right = 0, 0
        }
    }

    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Time and Space Complexity

ApproachTime ComplexitySpace ComplexityStackO(n)O(n)Two-PointerO(n)O(1)

Key Takeaways

• Stack-based solutions are great for tracking opening and closing parentheses.
• The two-pointer method is space-efficient and elegant.
• This problem helps sharpen your string parsing and edge case analysis skills.