32. Longest Valid Parentheses

-
https://leetcode.com/problems/longest-valid-parentheses/

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
---
Intuition
Traverse L to R
Save longest valid string via absolute counters
if open == closed => save max
if (closed > open) reset
Traversing L to R you can ignore prefix of string which is invalid

At the end of L to R traversal we've saved valid substring towards end of original string

Traverse R to L
if open == closed => save max
if (open > closed) reset
Traversing R to L you can ignore suffix of string which is invalid

Return the max saved
---
Time - O(N)
Space - O(1)
---
Related problems
---