Stack Topological Sort Simulation
Proficient Level

Implement the longestValidParenthesesLength method that returns the length of the longest valid parentheses substring.

You are given a string containing only opening and closing parentheses. Return the length of the longest continuous substring that forms a valid parentheses sequence.

The substring must be contiguous. For example, in )()()), the longest valid part is ()(), so the answer is 4.

Example 1
Input:
text (string) = )()())
Return:
(int) 4
Example 2
Input:
text (string) = (()
Return:
(int) 2
Example 3
Input:
text (string) = ()(())
Return:
(int) 6

Use a stack of indexes.

Keep a base index for the last unmatched closing bracket. When an opening bracket appears, push its index. When a closing bracket appears, pop one opening bracket if possible. The current valid length is the distance between the current index and the new top of the stack.

If the stack becomes empty after a closing bracket, push the current index as the new base.

Pseudocode:

function longestValidParenthesesLength(text):
    stack = [-1]
    best = 0
    for i from 0 to length of text - 1:
        if text[i] == '(':
            stack.push(i)
        else:
            stack.pop()
            if stack is empty:
                stack.push(i)
            else:
                best = max(best, i - stack.top)
    return best
Run your code to see the result.