Longest Valid Parentheses - Video Solutions

Problem Overview: You receive a string containing only ( and ). The task is to compute the length of the longest contiguous substring that forms a valid parentheses sequence.

Approach 1: Brute Force Validation (O(n^3) time, O(1) space)

The simplest idea is to check every possible substring and verify whether it forms a valid parentheses sequence. Iterate over all start indices and end indices, extract the substring, and validate it using a counter or small stack. A substring is valid if parentheses are balanced and never go negative during the scan. This approach demonstrates the core property of balanced parentheses but becomes extremely slow because it evaluates O(n^2) substrings and each validation may take O(n) time.

Approach 2: Stack-Based Index Tracking (O(n) time, O(n) space)

This is the most common solution using a stack. Store indices of unmatched parentheses. Initialize the stack with -1 as a sentinel to represent the start of a potential valid substring. Iterate through the string: push the index for every (. For ), pop the stack. If the stack becomes empty, push the current index as a new base. Otherwise compute the current valid length as i - stack.top(). The stack stores boundaries of invalid segments, allowing you to measure valid ranges efficiently while scanning the string.

Approach 3: Dynamic Programming (O(n) time, O(n) space)

The dynamic programming solution tracks the length of the longest valid substring ending at each index. Create an array dp[i] where dp[i] represents the longest valid parentheses substring ending at position i. When encountering ), two patterns may form: a direct pair () or a nested/extended structure like ...)). For the first case, set dp[i] = dp[i-2] + 2. For the second, check the character before the previous valid block and extend it if it forms a matching (. This approach uses dynamic programming to reuse previously computed valid segments and build longer ones.

Recommended for interviews: The stack solution is the most expected answer in interviews because it demonstrates clear reasoning about boundaries and invalid segments while maintaining O(n) time complexity. Dynamic programming is equally optimal and shows stronger algorithmic thinking, especially when explaining how valid substrings combine. Brute force rarely appears as a final solution but helps explain the constraints and why linear-time strategies are required.