0032. Longest Valid Parentheses

Interactive visualization of finding the longest valid parentheses substring

Stack Approach
DP Approach
Speed: 5
Stack Approach: Push indices onto the stack. Initialize with -1 as base. For each ), pop the top. If stack is empty, push current index as new base. Otherwise, maxLen = i - stack.top. Time: O(n), Space: O(n)
maxLen = 0
Stack (indices)
empty
Click "Step" or "Play" to begin...
Waiting to start...
DP Approach: dp[i] = length of longest valid substring ending at index i. Case 1: s[i-1]=='(' then dp[i] = dp[i-2] + 2. Case 2: s[i-1]==')' and s[i-dp[i-1]-1]=='(' then dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]. Time: O(n), Space: O(n)
maxLen = 0
Waiting to start...
dp[] array
Click "Step" or "Play" to begin...
Waiting to start...