Length of the Longest Valid Substring

Problem Statement

Given a string containing just '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example:

Approach 1: Brute Force

Intuition

Generate all possible substrings and check if each is a valid parentheses string. Track the maximum length among valid ones.

Algorithm

1. For each starting position i
2. For each ending position j > i (even length only)
3. Check if substring(i, j) is valid
4. Track maximum length

public class LongestValidParentheses {
    private static boolean isValid(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') count++;
            else count--;
            if (count < 0) return false;
        }
        return count == 0;
    }
    
    public static int longestValidParenthesesBruteForce(String s) {
        int maxLen = 0;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 2; j <= n; j += 2) {
                if (isValid(s.substring(i, j))) {
                    maxLen = Math.max(maxLen, j - i);
                }
            }
        }
        
        return maxLen;
    }
}

Complexity Analysis

• Time Complexity: O(n^3) - O(n^2) substrings, O(n) to validate each
• Space Complexity: O(n) - for substring creation

Approach 2: Using Stack (Optimal)

Intuition

Use a stack to track indices of unmatched parentheses. Push index of '(' and pop when ')' matches. The length of valid substring is current index minus the index at stack top (which marks the end of last invalid portion).

Algorithm

1. Initialize stack with -1 (base for calculating length)
2. For each character:
   • If '(': push its index
   • If ')':
     • Pop from stack
     • If stack empty: push current index (new base)
     • Else: calculate length = i - stack.top()
3. Track maximum length

import java.util.*;

public class LongestValidParentheses {
    public static int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);  // Base for length calculation
        int maxLen = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                
                if (stack.isEmpty()) {
                    // No matching '(', push current as new base
                    stack.push(i);
                } else {
                    // Valid match found, calculate length
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        
        return maxLen;
    }
    
    public static void main(String[] args) {
        System.out.println(longestValidParentheses("(()"));      // 2
        System.out.println(longestValidParentheses(")()())"));   // 4
        System.out.println(longestValidParentheses("()(())"));   // 6
    }
}

Complexity Analysis

• Time Complexity: O(n) - single pass through the string
• Space Complexity: O(n) - stack can hold up to n indices

Approach 3: Two Pass (O(1) Space)

Intuition

Instead of using a stack, use two counters for left and right parentheses. Scan left-to-right and right-to-left to handle different cases.

Trace Example

For string ")()())":

Key Takeaways

1. Stack stores indices of unmatched parentheses, not characters
2. The -1 base is crucial for calculating length when all previous chars are matched
3. When stack becomes empty after pop, current ')' is unmatched - use it as new base
4. Two-pass approach achieves O(1) space but is less intuitive
5. This problem combines stack usage with length tracking
6. Common pattern: track position of last invalid element to compute valid substring length