Longest Valid Route Through an API Gateway

Problem Statement

An API gateway receives a routing string made only of '(' and ')', where '(' means "enter a nested route scope" and ')' means "exit a scope." A valid route is a properly balanced sequence of scopes.

Given the routing string, find the length of the longest contiguous valid (well-balanced) route.

Constraints

• 0 <= routes.length <= 10^5
• String contains only '(' and ')'
• "Valid" means every open scope has a matching close in correct order

Example

Input: routes = ")()())"

Output: 4

Explanation: The longest valid contiguous substring is "()()" (length 4).

Input: routes = "(()"

Output: 2

The Insight — Stack of Indices (or DP)

Two elegant O(n) approaches:

Approach 1 — Stack of indices:

• Push index -1 as a base marker.
• For '(', push its index.
• For ')', pop. If the stack becomes empty, push the current index as a new base. Otherwise, the current valid length = currentIndex - stackTop.
• Track the max length seen.

The "aha": the stack doesn't hold the parentheses — it holds boundary indices, so the distance from the current position to the last unmatched boundary gives the valid length instantly.

Approach 2 — DP:

• dp[i] = length of the longest valid substring ending exactly at index i.
• Only compute dp[i] when routes[i] == ')', using the matched opening position and chaining with dp before it.

Both are O(n) time. The stack version is the one that makes people go "oh, clever — track boundaries, not brackets."

Follow-ups

1. Why push -1 as the initial stack element? What does it represent?
2. Can you solve it in O(1) space using two counters (left/right scan both directions)?
3. What if there were multiple bracket types ([], {})? Does the stack approach still give longest valid?
4. What if you needed the actual substring, not just its length?