Length of the longest valid parentheses substring
Problem
Given a string of "(" and ")", return the length of its longest substring that is well-formed (balanced).
Example 1
Input: "(()" Output: 2
Example 2
Input: ")()())" Output: 4
"()()".
Also asked as: Length of the Longest Valid Substring
Test cases
Case 1
Input: "(()" Expected: 2
Case 2
Input: ")()())" Expected: 4
Case 3
Input: "()(())" Expected: 6
Case 4
Input: "(("
Expected: 0Case 5
Input: "" Expected: 0
View solutionHide solution1 approach
1. Stack of indices with a base marker
Time O(n)Space O(n)
Push −1 as a base. On "(", push its index. On ")", pop; if the stack is now empty push this index as the new base, else the current valid length is i − stack top.
function longestValidParentheses(s) { const st = [-1]; let best = 0; for (let i = 0; i < s.length; i++) { if (s[i] === '(') st.push(i); else { st.pop(); if (st.length === 0) st.push(i); else best = Math.max(best, i - st[st.length - 1]); } } return best;}