Leetcode 32: Longest Valid Parentheses

 

1. Problem Statement (Simple Explanation):

You are given a string s containing only:

• '('

• ')'

You must return the length of the longest valid (well-formed) parentheses substring.

• A valid substring must be contiguous.

• It must be a correct parentheses sequence (every '(' has a matching ')' in proper order).

2. Examples:

Example 1:

Input: s = "(()"

Valid substrings:

• "()" (from index 1 to 2) – length 2

Longest length: 2

Output: 2

Example 2:

Input: s = ")()())"

Valid substrings:

• "()()" (from index 1 to 4) – length 4

• "()" (from index 1 to 2)

• "()" (from index 3 to 4)

Longest length: 4

Output: 4

Example 3:

Input: s = ""

No parentheses → no valid substring.

Output: 0

Constraints:

• 0 ≤ ∣s∣ ≤ 3*104

• s[i] is '(' or ')'.

3. Approaches Overview:

There are three classic approaches:

1. Stack-based – O(n) time, O(n) space.

2. Two-pass counters (left-to-right and right-to-left) – O(n) time, O(1) space.

3. Dynamic programming – O(n) time, O(n) space.

4. Approach 1 – Stack with Indices (O(n), Easy to Reason):

Intuition:

• Use a stack that stores indices of characters.

• Use it to track boundaries between valid substrings.

Trick:

• Push -1 initially to represent a "base" before the start of the string.

• When you see '(', push its index.

• When you see ')':

• Pop the stack (matching a previous '(' if possible).

• If the stack becomes empty after popping:

• Push current index as a new base (this ')' is an unmatched right boundary).

• Else:

• Current valid substring length = i - stack.top()

• Update max.

This works because:

• stack.top() always holds the index just before the start of the current valid segment.

Algorithm (Step-by-Step):

1. Initialize:

• maxLen = 0

• Stack st

• Push -1 onto st (base index).

2. For each index i in 0..n-1:

• If s[i] == '(':

• Push i onto stack.

• Else (s[i] == ')'):

• Pop the stack:

• If stack becomes empty:

• Push i as a new base.

• Else:

• len = i - st.top()

• maxLen = max(maxLen, len)

3. Return maxLen.

Pseudo-code (Stack):

Complexity:

• Time: O(n)

• Space: O(n) in worst case (all '(').

5. Approach 2 – Two-pass Scan with Counters (O(n), O(1) Space):

This is a very elegant solution and space-optimal.

Intuition:

We track counts of '(' and ')' while scanning:

1. Left to Right:

• left = 0, right = 0

• For each char:

• If '(' → left++

• If ')' → right++

• If left == right:

• Valid substring length = 2 * right

• If right > left:

• Reset both counts to 0 (too many ')' → invalid).

This catches valid segments where we never see more ')' than '(' (like well-formed from the left). But it misses cases that end with more '(' (like "(()"), since we only reset on extra ')'.

2. Right to Left:

• Same idea, but swap roles:

• left = 0, right = 0

• Scan from right to left:

• If '(' → left++

• If ')' → right++

• If left == right:

• Valid substring length = 2 * left

• If left > right:

• Reset both counts (too many '(' from this side).

Combining both scans handles all cases.

Pseudo-code (Two-pass):

Complexity:

• Time: O(n)

• Space: O(1)

6. Java (Stack Solution) code:

7. C (Stack via Array) code:

8. C++ (Stack) code:

9. Python (Stack) code:

10. JavaScript (Stack) code: