Longest Well-Formed Stretch
HardStack
Problem
A log of ( and ) characters s got corrupted. Find the longest contiguous substring that is still a well-formed parenthesis sequence (every ( matched by a later ), properly nested).
Return its length, or 0 if there is none.
Example 1
- Input:
- s = "(()"
- Output:
- 2
The substring "()" at positions 1–2.
Example 2
- Input:
- s = ")(()())"
- Output:
- 6
Everything after the first character.
Example 3
- Input:
- s = "())(())"
- Output:
- 4
Constraints
- 0 ≤ s.length ≤ 3·10^4
- s contains only '(' and ')'
Hint
Show the first hint
Matching a ')' with its '(' is the usual stack job. What does the stack tell you about where the current valid stretch begins?
Walkthrough
How to approach it
01Clarify before coding
- Substring or subsequence? A contiguous substring.
- Do I return the substring or its length? Only the length.
- Empty input? Return 0.
02Brute force
Check every even-length substring with a balance counter and keep the longest valid one.
Cost: O(n²) substrings, each checked in O(n) — O(n³), or O(n²) if you extend each start incrementally: 9·10^8 for n = 3·10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.