Longest Valid Parentheses

hard string dp stack

Problem

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

Inputs = "(()"

Output2

The longest valid substring is "()".

def longest_valid_parentheses(s):
    stack = [-1]
    best = 0
    for i, c in enumerate(s):
        if c == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

function longestValidParentheses(s) {
  const stack = [-1];
  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);
      else best = Math.max(best, i - stack[stack.length - 1]);
    }
  }
  return best;
}

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        int best = 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 best = Math.max(best, i - stack.peek());
            }
        }
        return best;
    }
}

int longestValidParentheses(string s) {
    stack<int> st;
    st.push(-1);
    int best = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') st.push(i);
        else {
            st.pop();
            if (st.empty()) st.push(i);
            else best = max(best, i - st.top());
        }
    }
    return best;
}

Explanation

We want the longest stretch of balanced parentheses. The neat trick is to keep a stack of indices that marks the boundary just before the current valid run, so the length of a valid stretch is simply the gap between the current index and the last unmatched position.

We seed the stack with -1 as a base boundary. For every '(' we push its index. For every ')' we pop one entry, treating it as a match.

After popping, if the stack became empty, this ')' had no partner, so we push its own index as a new boundary. Otherwise the top now holds the index just before the current valid run, and the length is i - stack[-1], which we compare against best.

This works because each unmatched character resets the boundary, and the distance from the current position back to the most recent unmatched spot is exactly the length of the longest valid run ending here.

Example: for "(()", the stack starts [-1]; we push 0 and 1 for the two (, then the ) at index 2 pops 1, leaving top 0, giving 2 - 0 = 2 — the answer.

Time: O(n) Space: O(n)