hard Longest Valid Parentheses

Problem Statement

You are given a string containing just the characters '(' and ')'. Your task is to find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(())"
Expected Output: 4
Justification: The entire string is a valid parentheses substring.

Example 2:

Input: ")()())"
Expected Output: 4
Justification: The longest valid parentheses substring is "()()".

Example 3:

Input: "(()"
Expected Output: 2
Justification: The longest valid parentheses substring is "()".

Constraints:

0 <= s.length <= 3 * 10⁴
s[i] is '(', or ')'.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Longest Valid Parentheses — problem

0. Pattern family

Family: Stack of indices / DP ends-at-i

1. Why / judgment (K3)

Longest substring of valid parentheses (not subsequence). Stack of indices: push −1 base; on ‘(’ push i; on ‘)’ pop then if stack empty push i else max_len = max(i−stack.top()). DP: if s[i]=')' pair with previous; dp[i] chains. Judgment: stack length counter alone fails on ")()()" vs "()(()" — indices needed for substring length.

2. Worked complexity / derivation (K11)

O(n) time O(n) stack/DP space.
Two-pass counter L→R R→L also O(n)/O(1) for this problem.

3. Pattern + recognition + when-NOT (K12)

Name: STACK INDICES / DP — LONGEST VALID PARENTHESES SUBSTRING

Recognition: string of () only; longest valid contiguous substring length.

When-NOT: If any brackets type → stack validity different objective. If longest subsequence → remove min. If count valid total splits → catalan-related different.

4. Edge hand-run (K13)

"(()" →2. ")()())" →4. "" →0. "()(()" →2.
Edge: all '(' →0. single ')' →0.

5. Interviewer follow-ups & drills

Q1. Why push −1?
Model answer: Base boundary so length of full valid prefix computes as i−(−1).

Q2. Empty stack after pop?
Model answer: Push current i as new base invalid boundary.

Q3. DP transition?
Model answer: dp[i]=dp[i-1]+2 + dp[i-dp[i-1]-2] when matching.

✅ Solution Longest Valid Parentheses

Problem Statement

You are given a string containing just the characters '(' and ')'. Your task is to find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(())"
Expected Output: 4
Justification: The entire string is a valid parentheses substring.

Example 2:

Input: ")()())"
Expected Output: 4
Justification: The longest valid parentheses substring is "()()".

Example 3:

Input: "(()"
Expected Output: 2
Justification: The longest valid parentheses substring is "()".

Constraints:

0 <= s.length <= 3 * 10⁴
s[i] is '(', or ')'.

Solution

Understanding the Problem:
- The problem involves finding the longest sequence of valid parentheses.
- A stack data structure can be used to keep track of the indices of the invalid parentheses.
Approach:
- Initialize a stack and push -1 onto it as a marker for the base.
- Iterate through the string and for each character:
  - If it is '(', push its index onto the stack.
  - If it is ')', pop an element from the stack.
    - If the stack is not empty, calculate the length of the valid parentheses substring by subtracting the current index with the top of the stack.
    - If the stack is empty, push the current index onto the stack to serve as the new base marker.
Why This Approach Will Work:
- The stack keeps track of the indices of invalid parentheses, allowing us to easily calculate the length of valid substrings.
- By continuously calculating the length and updating the maximum length, we ensure finding the longest valid substring.

Algorithm Walkthrough

Consider the input ")()())":

Initialize stack with -1: stack = [-1]
Iterate through the string:
- At index 0: ')'
  - Pop from stack: stack = []
  - Stack is empty, push index 0 onto stack: stack = [0]
- At index 1: '('
  - Push index 1 onto stack: stack = [0, 1]
- At index 2: ')'
  - Pop from stack: stack = [0]
  - Calculate length: 2 - 0 = 2
- At index 3: '('
  - Push index 3 onto stack: stack = [0, 3]
- At index 4: ')'
  - Pop from stack: stack = [0]
  - Calculate length: 4 - 0 = 4
- At index 5: ')'
  - Pop from stack: stack = []
  - Stack is empty, push index 5 onto stack: stack = [5]
The longest valid parentheses substring is of length 4.

Code

java

import java.util.Stack;

public class Solution {

  public int longestValidParentheses(String s) {
    int max = 0; // To keep track of the maximum length
    Stack<Integer> stack = new Stack<>(); // Stack to keep track of indices
    stack.push(-1); // Initial value to calculate length properly
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      if (c == '(') {
        stack.push(i); // Push the index of '(' to stack
      } else {
        stack.pop(); // Pop from stack for ')'
        if (stack.isEmpty()) {
          stack.push(i); // Reset the base for length calculation
        } else {
          max = Math.max(max, i - stack.peek()); // Calculate the length
        }
      }
    }
    return max;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    // Testing the function with example inputs
    System.out.println(sol.longestValidParentheses("(())")); // Output: 4
    System.out.println(sol.longestValidParentheses(")()())")); // Output: 4
    System.out.println(sol.longestValidParentheses("(()")); // Output: 2
  }
}

Complexity Analysis

Time Complexity: O(n), where n is the length of the input string. The algorithm traverses the string once.
Space Complexity: O(n), where n is the length of the input string. In the worst case, the stack will store all characters of the string.

🎯 STRICT STANDOUT — Solution Longest Valid Parentheses

0. Pattern family

Family: Stack of indices / DP ends-at-i

1. Why / judgment (K3)

2. Worked complexity / derivation (K11)

O(n) time O(n) stack/DP space.
Two-pass counter L→R R→L also O(n)/O(1) for this problem.

3. Pattern + recognition + when-NOT (K12)

Name: STACK INDICES / DP — LONGEST VALID PARENTHESES SUBSTRING

Recognition: string of () only; longest valid contiguous substring length.

When-NOT: If any brackets type → stack validity different objective. If longest subsequence → remove min. If count valid total splits → catalan-related different.

4. Edge hand-run (K13)

"(()" →2. ")()())" →4. "" →0. "()(()" →2.
Edge: all '(' →0. single ')' →0.

5. Interviewer follow-ups & drills

Q1. Why push −1?
Model answer: Base boundary so length of full valid prefix computes as i−(−1).

Q2. Empty stack after pop?
Model answer: Push current i as new base invalid boundary.

Q3. DP transition?
Model answer: dp[i]=dp[i-1]+2 + dp[i-dp[i-1]-2] when matching.

🧩 Pattern · Stack

Recognize it: Matching / nesting, or “next greater / smaller” → LIFO, or a monotonic stack.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Longest Valid Parentheses? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Longest Valid Parentheses** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Longest Valid Parentheses** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Longest Valid Parentheses**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Longest Valid Parentheses**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← First Missing Positive Solution Take Gifts From the Riche →