LeetCode #32: Longest Valid Parentheses — Solved in Java

Stack of Indices and Two Pass Counter Scan

Image Source

The Longest Valid Parentheses LeetCode problem asks for the length of the longest well-formed block of parentheses in a given string. Java code for this problem needs to spot stretches where opening and closing symbols line up and ignore regions where the balance breaks. The tricky part comes from the fact that valid spans can appear anywhere in the string, and broken regions can interrupt them without warning.

Thinking about this problem in Java works best when you focus on how balance forms and how it breaks. A well-formed span always has the same count of ‘(’ and ‘)’ by the time it closes, yet keeping track of where that balance starts matters just as much. Java gives you a few clean structures to track that balance. You can use a stack of indices to anchor each open parenthesis, or you can walk the string with counters from both directions to catch balanced stretches without extra memory. Both views come from the same mindset of watching how the balance shifts step by step while ignoring any fragments that can’t support a valid block.

LeetCode: Longest Valid Parentheses

Given a string containing just the characters ‘(’ and ‘)’, return the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: s = “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”.

Example 2:

Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.

Example 3:

Input: s = “”
Output: 0

Constraints:

• 0 <= s.length <= 3 * 10^4

• s[i] is ‘(’, or ‘)’.

I usually include the full code as a screenshot to make it easier to read on phones since Substack’s code formatting can be tough to follow on smaller screens. Hard solutions tend to be much longer than usual though, so capturing everything in one image isn’t always practical. You can still copy and run the complete solutions below, and at the end of the article you’ll find the same full code again with added comments to help follow along.

Solution 1: Stack of Indices

This solution follows the classic stack idea and stores indices instead of characters. A sentinel index anchors the start of a potential valid span, and each time a closing parenthesis finishes a valid region, the code measures how far back that span reaches.