LeetCode-in-All
32. Longest Valid Parentheses
Hard
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”.
Example 2:
Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.
Example 3:
Input: s = “”
Output: 0
Constraints:
0 <= s.length <= 3 * 104s[i]is'(', or')'.
Solution
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function (s) {
const n = s.length
const f = new Array(n + 1).fill(0)
for (let i = 2; i <= n; ++i) {
if (s[i - 1] === ')') {
if (s[i - 2] === '(') {
f[i] = f[i - 2] + 2
} else {
const j = i - f[i - 1] - 1
if (j && s[j - 1] === '(') {
f[i] = f[i - 1] + 2 + f[j - 1]
}
}
}
}
return Math.max(...f)
};
export { longestValidParentheses }