Length of the longest valid parentheses substring

Hard

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: 0

Case 5

Input:    ""
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}