The O(n) Club: Surviving the Longest Valid Parentheses Without Therapy

The O(n) Club: Surviving the Longest Valid Parentheses Without Therapy

⚡ TL;DR

You get a string of ‘(‘ and ‘)’. Your mission: find the length of the longest consecutive valid parentheses substring—so you can stop arguing with your code editor and maybe finally pass that technical screen. Like pain, brute force is O(n³); but if you aren’t looking to fry your CPU, here’s a lightning-fast (and stack-powered) Java sample:

// Java quick-draw solution
the Stack
<integer> stack = new Stack<>();
stack.push(-1); // Invisible anchor
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
    if (s.charAt(i) == '(') stack.push(i);
    else {
        stack.pop();
        if (stack.isEmpty()) stack.push(i);
        else maxLen = Math.max(maxLen, i - stack.peek());
    }
}
</integer>

🧠 How Devs Usually Mess This Up

Straight out of Stack Overflow’s Hall of Fame: people go brute-force, checking every substring, looking for complete validity. That’s about as efficient as manually pairing your socks every morning. Others try validating the whole string—congrats, you’ll miss streaks like ‘()()’. Also, if you’re just popping pairs (instead of storing indices), your algorithm will be as lost as a debugger at 2 AM.

🔍 What’s Actually Going On

Think of your compiler as an overworked chef, stacking dirty dishes—‘(’ stacks up, ‘)’ lets him clean one off. You want the chef’s longest run without dropping any plates, i.e., the deepest valid substring. Instead of pairing plates, you’re marking positions in the stack. Each time a match finishes, check how much distance you’ve covered since the last troublemaker, thanks to your stack of indices. Voilà: clean parentheses and a happy kitchen.

🛠️ PseudoCode

• Start with an empty kitchen: stack.push(-1) (so your chef knows where to start counting).
• Sweep through each char in the input:
  • If it’s ‘(‘, push that index into the stack—the chef stacks another plate.
  • If it’s ‘)’, pop the stack (the chef cleans a plate). If the stack is empty (chef fumbles), push index as a new baseline.
  • If plates remain, the stretch is i - stack.peek(). Update your longest streak.
• Return your longest valid dishes—err, substring—count.

💻 The Code

import java.util.*;
public class LongestValidParentheses {
    public static int longestValidParentheses(String s) {
        Stack
<integer> stack = new Stack<>();
        stack.push(-1); // Start baseline
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    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(""));         // 0
    }
}
</integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Edge Case Ghosts: Don’t forget empty string (“”), all opening (“(((“), or all closing (“)”) inputs—they should all yield 0, not a stack trace.
• Stack Underflow: Your stack’s -1 isn’t weird; it’s your edge-case parachute.
• Counting Chars Instead of Indices: Won’t work—trust me, I’ve lost more interviews this way than I care to admit.
• Complexity: It’s O(n) time and O(n) space. Anything slower, and the ghost of Turing will haunt your IDE.

🧠 Interviewer Brain-Tattoo

“Brute force is for machines. Stacks and indices? That’s for humans pretending to be machines.”