#data-structure/stack #algo/prefix-sum ## Notes - If a subsequence $s$ is valid, then we have for $s':=s[..k]$ for any $k \leq ||s||$, there are more opening braces than closing braces. - We do a left-to-right scan, when the invariant breaks, we set things to zero. - We perform a right-to-left scan as well. Similarly, there is this invariant: if a subsequence $s$ is valid, we have for any $s'':=[k..]$ for any $k \leq ||s||$, there are more closing braces than opening braces. - We need to perform both left-to-right and right-to-left because there may be more opening than closing ones. Doing so resolves this issue. ## Problem ### Problem Description Given a string containing just the characters `'('` and `')'`, return the length of the longest valid (well-formed) parentheses substring. ### Examples #### 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 * 10^4` - `s[i]` is `'('` or `')'`.