4.2 Expression Evaluation / Parentheses

Demo: Longest Valid Parentheses — LC 32 (Hard — Google High)

Statement (Demo): Given a string s of only '(' and ')', return the length of the longest valid parentheses substring. Example: s=")()())" → 4 | ⚡ len ≤ 3×10⁴

Approach: Keep indices on a stack with -1 at the bottom as a base. Push on (. On ) pop — if the stack is now empty, this ) becomes the new base; otherwise the current valid length is i - stack.top.

function longestValidParentheses(s) {
  const stack = [-1]; // base index
  let best = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") stack.push(i);
    else {
      stack.pop();
      if (stack.length === 0)
        stack.push(i); // new base
      else best = Math.max(best, i - stack[stack.length - 1]);
    }
  }
  return best;
}

Complexity: Time O(n), Space O(n)