Find the longest valid () substring in O(n)
Implement longestValidParentheses(s) returning the length of the longest substring of correctly nested (). Requirements: O(n) time, single pass over the string. Handle the edge cases — an empty string and a string with no valid pair both return 0; unmatched ) and unmatched ( break the current run. Examples: "(()" → 2, ")()())" → 4.
func longestValidParentheses(s string) int {
// your code here
return 0
}Write the implementation.
Push a sentinel index -1, then for each ( push its index and for each ) pop. After a pop, if the stack is non-empty the current valid run length is i - stack[top]; if it emptied, push i as the new base. Track the running maximum — O(n) time, O(n) space.
- ✗Storing characters instead of indices — length cannot be computed without positions
- ✗Forgetting the
-1sentinel, which is what makesi - stack[top]give the right length - ✗Pushing the index after an emptying pop instead of using it as the new base offset
- →How does the two-counter left-and-right pass solve this in O(1) space?
- →Why must the index of an unmatched
)become the new stack base?
Task
Given a string of ( and ), find the length of the longest correctly nested substring. The stack holds indices, not characters.
func longestValidParentheses(s string) int {
best := 0
stack := []int{-1} // sentinel: base for measuring a run
for i := 0; i < len(s); i++ {
if s[i] == '(' {
stack = append(stack, i)
} else {
stack = stack[:len(stack)-1] // pop
if len(stack) == 0 {
stack = append(stack, i) // unmatched ')' — new base
} else if run := i - stack[len(stack)-1]; run > best {
best = run
}
}
}
return best
}The -1 sentinel lets the length be computed as i - stack[top]. An unmatched ) empties the stack and becomes the new base offset. Complexity is O(n) time and O(n) space.
