Longest Valid Parentheses

Given a string containing just the characters ( and ), return the length of the longest valid parentheses substring.

Example:

• Input: (() -> Output: 2 (substring ()).
• Input: )()()) -> Output: 4 (substring ()()).

We can use a Stack to store indices. The stack will help us calculate the length of valid substrings by tracking the 'base' index from which validity starts.

1. Initialize stack with -1. This acts as a base index for a valid substring starting at 0.
2. Iterate through string at index i:
3. If (: push(i).
4. If ): pop().
   • If stack is empty: push(i). The current ) is invalid and becomes the new base.
   • If stack not empty: maxLen = max(maxLen, i - stack.top()). The valid substring is from stack.top() + 1 to i.

Visualize how storing indices helps calculate length. -1 is our initial base.