Longest Valid Parentheses

Longest Valid Parentheses

What is this problem about?

The Longest Valid Parentheses problem is a notorious string parsing challenge. Given a string containing just the characters ( and ), you must find the length of the longest contiguous substring that forms a valid, well-formed parentheses sequence. For example, in the string ")()())", the longest valid substring is "()()", which has a length of 4.

Why is this asked in interviews?

This is a premier Hard-level problem that tests a candidate's mastery of the Stack data structure and edge-case management. It is asked by top-tier tech companies because handling malformed syntax is a core requirement for building compilers, parsers, and IDEs. It forces candidates to think about how to track boundaries and sequence resets when invalid characters disrupt the flow.

Algorithmic pattern used

While Dynamic Programming is an option, the Stack pattern is the most robust and intuitive. You use a Stack to store the indices of the characters, not the characters themselves. Crucially, you initialize the stack by pushing -1 onto it. This -1 acts as a base boundary for the valid sequence. When you see (, push its index. When you see ), pop the stack. If the stack is empty after popping, push the current index (it's the new invalid boundary). If not empty, the current length is current_index - stack.peek().

Example explanation

String: ")()())" Initialize Stack: [-1]

• Index 0 ): Pop stack. Stack is empty. Push current index 0. Stack: [0]. (New boundary).
• Index 1 (: Push index 1. Stack: [0, 1].
• Index 2 ): Pop stack (pops 1). Stack is [0]. Valid length = 2 - stack.peek(0) = 2. Max = 2.
• Index 3 (: Push index 3. Stack: [0, 3].
• Index 4 ): Pop stack (pops 3). Stack is [0]. Valid length = 4 - stack.peek(0) = 4. Max = 4.
• Index 5 ): Pop stack (pops 0). Stack is empty. Push current index 5. Stack: [5]. The longest valid sequence was 4.

Common mistakes candidates make

Candidates frequently use a standard parentheses validation trick (tracking a simple count variable where ( is +1 and ) is -1). While this works to check if a whole string is valid, it fails to find the length of contiguous valid substrings because it loses track of where the valid segment started. Another mistake is storing the characters ( in the stack rather than their integer indices, making length calculations impossible.

Interview preparation tip

To crush the Longest Valid Parentheses coding problem, memorize the trick of initializing your index-stack with -1. This "dummy index" seamlessly handles the math for valid sequences that start at the very beginning of the string (index 0), preventing 0 - 0 = 0 errors and resulting in the correct length of 0 - (-1) = 1.