Abstract / Summary

Find the length of the longest correctly matched group of parentheses in a string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 39% (2+ million submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Stack
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements two distinct algorithms for computing the length of the longest contiguous substring of well-formed parentheses. The first method, longestValidParentheses_old, builds a depth map of the input and then uses the first and last positions of each depth to locate candidate intervals. The second method, longestValidParentheses, repeatedly collapses matching pairs and adjacent integer markers in a mutable list until no further reductions are possible, finally extracting the maximum integer value.

Both approaches operate directly on the input string without auxiliary data structures such as stacks, and each contains specific handling for edge conditions such as empty inputs, strings that never achieve a balanced depth, and nested or interleaved parentheses patterns.

Detailed Walkthrough of longestValidParentheses_old

The algorithm begins by handling trivial inputs.

size = len(s)
if size < 2:
    return 0

When the string length is less than two, a valid pair cannot exist, so the function returns zero immediately.

Depth Construction

An offset of 100000 is added to the depth counter to keep the value non-negative throughout the scan. This eliminates the need for explicit checks against negative depths during the main loop.

offset = 100000
depth = offset
nesting = []
for c in s:
    if c == "(":
        depth += 1
        nesting.append(depth)
    else:
        nesting.append(depth)
        if depth > 0:          # negative always invalid
            depth -= 1

Each character contributes a depth entry: an opening parenthesis increments the depth, while a closing parenthesis records the current depth before potentially decrementing it. The comment clarifies that a depth of zero (the offset) signals an invalid state for a closing parenthesis, ensuring that the depth never drops below the offset.

First and Last Position Tracking

Two dictionaries, first and last, capture the earliest opening parenthesis and the latest closing parenthesis for each distinct depth value.

first = {}
last  = {}
for n in range(size):
    current = nesting[n]
    if current == 0:
        continue
    if s[n] == "(" and current not in first:
        first[current] = n
    if s[n] == ")":
        last[current] = n

The loop skips entries where the depth equals zero because they cannot be part of a valid substring. For each depth, the first occurrence of '(' is stored only once, while the most recent occurrence of ')' overwrites any previous entry, guaranteeing that first holds the leftmost opening index and last holds the rightmost closing index for that depth.

Candidate Interval Evaluation

The algorithm iterates over each depth present in first. If a matching entry exists in last, the interval between the two indices is examined.

best = 0
for i in first:
    if i in last:
        left  = first[i]
        right = last[i]
        distance = right - left + 1
        if distance > 1 and best < distance:
            ok = True
            for x in range(left, right):
                if nesting[x] < nesting[left]:
                    ok = False
                    break
            if ok:
                best = distance

The inner loop validates that the depth never falls below the depth at the left boundary throughout the interval, confirming that the substring is properly nested. If the check passes, best is updated with the interval length.

Edge Cases Handled

• Empty or single-character strings return zero early.
• Strings that never achieve a positive depth (e.g., ")(") are ignored because current == 0 entries are skipped.
• Nested structures are correctly identified because the depth never drops below the left boundary within a valid interval.
• Disjoint valid substrings are considered separately via distinct depth keys.

Implicit Optimizations

• The offset technique removes the need for conditional branches that would otherwise handle negative depth values.
• Storing only the first opening index and the last closing index per depth reduces the number of interval checks.
• The early continue for zero depth avoids unnecessary dictionary updates.
• The inner validation loop exits as soon as an invalid depth is detected, preventing full scans of obviously invalid intervals.

Detailed Walkthrough of longestValidParentheses

The second method adopts an iterative reduction strategy that transforms the input string into a mutable list of characters and integer markers representing the lengths of already validated substrings.

List Initialization

size = len(s)

brackets = []
for c in s:
    brackets.append(c)

The input string is copied into a list named brackets. This list will be mutated in place, allowing deletions and replacements without creating new containers.

Iterative Reduction Loop

A flag again controls the outer loop, ensuring that the process repeats only while changes occur.

again = True
iterations = 0
while again:
    again = False
    iterations += 1
    i = 0
    while i < size:
        # pattern checks and transformations
        i += 1

The inner loop walks through the list using an index i. Three pattern recognitions drive the transformations:

1. Immediate Pair () When a '(' is directly followed by a ')', the pair is replaced by the integer 2, and the closing parenthesis is removed.

   if i+1 < size and brackets[i] == "(" and brackets[i+1] == ")":
       brackets[i] = 2
       del brackets[i+1]
       size -= 1
       again = True

2. Adjacent Integers Two consecutive integer markers are merged by summing their values, effectively concatenating two previously validated substrings.

   elif i+1 < size and type(brackets[i]) == int and type(brackets[i+1]) == int:
       brackets[i] += brackets[i+1]
       del brackets[i+1]
       size -= 1
       again = True

3. Enclosed Integer (int) A pattern where an opening parenthesis precedes an integer marker and a closing parenthesis follows is collapsed into a single integer representing the enclosed length plus the surrounding pair.

   elif i+2 < size and brackets[i] == "(" and type(brackets[i+1]) == int and brackets[i+2] == ")":
       brackets[i] = brackets[i+1] + 2
       del brackets[i+2]   # delete order is important !
       del brackets[i+1]
       size -= 2
       again = True

Each transformation reduces the list size and sets again to True, prompting another pass to catch newly formed patterns that may have emerged after the modification.

Extraction of the Maximum Length

After no further reductions are possible, the list contains a mixture of characters (unmatched parentheses) and integer markers (lengths of valid substrings). The final scan selects the largest integer.

best = 0
for b in brackets:
    if type(b) == int:
        best = max(best, b)
return best

Edge Cases Handled

• Strings without any matching pairs leave the list unchanged, resulting in a best value of zero.
• Nested structures such as "((()))" are reduced stepwise: inner pairs become 2, then the enclosing pattern (2) becomes 4, and finally the outermost pattern (4) becomes 6.
• Interleaved unmatched parentheses, for example "())(()", are partially reduced where possible, while stray characters remain and do not affect the integer markers.
• Consecutive valid substrings like "()()" are merged through the adjacent integer rule, yielding a single integer 4.

Implicit Optimizations

• The use of a mutable list avoids the overhead of constructing new strings on each reduction.
• The size variable is updated in sync with deletions, preventing repeated length calculations.
• The again flag ensures that the outer loop terminates as soon as a full pass produces no changes, eliminating unnecessary iterations.
• Merging adjacent integers early reduces the number of elements the inner loop must examine in subsequent passes.

Comparative Observations

Both implementations avoid explicit stack usage, opting instead for depth tracking or in-place list manipulation. The first method leverages depth indices to locate candidate intervals in a single pass, while the second method repeatedly simplifies the structure until only length markers remain. Each approach includes safeguards for empty inputs, unmatched parentheses, and nested configurations, and each incorporates subtle performance tricks-offset depth to sidestep negative checks, dictionary lookups for first/last positions, and mutable list reductions with a change-driven loop-to keep the runtime efficient without sacrificing correctness.

Imagine you have a long string of open and closed parentheses. The goal of this code is to find the longest group that is perfectly matched, like a set of closed loops where every opening sign has a closing friend right next to it.

The code starts by looking at the whole string like a long line of individual characters. It goes through the line over and over again to clean it up. Every time it spots an opening parenthesis right next to a closing one, it marks them as a pair. It keeps joining these pairs together as it searches through the line. Think of this like matching socks. If there is an open sock and a closed sock, they snap together. Then, if there are two pairs next to each other, they get connected into a bigger group of four.

The computer keeps running through the line, repeating this process of shrinking the line and connecting the neighbors. It does this until no more pairs can be found to snap together. By the time it stops, the group that was a pair of socks has turned into a count of how many pieces are in that set. All the parts of the string that were successfully matched now carry a number representing how long that matched group is. Finally, the code looks at all those numbers and picks the biggest one to show how many parentheses were part of the longest successful group.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java									TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python	C#	Java	Rust	JS				Go		PHP	TS
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	AdelDaniel											Dart
	aylei					Rust
	begeekmyfriend							C
	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai				Java
	chenyanzhe	C++
	everthis						JS
	fartem									Ruby
	FelixFan1122			C#
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan				Java
	halfrost										Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	martianoff								Scala
	qiyuangong		Python
	ruoru					Rust
	shreymehul			C#
	suxrobGM			C#
	trung-hn		Python
	varunu28				Java
	vli02							C
	wisdompeak	C++
	XiaotaoGuo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
martianoff	Scala
qiyuangong	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
wisdompeak	C++
XiaotaoGuo	C++

This is my lowest quality solution (hard) with an average rating of 3.6.

Longest explanation with 8799 characters.

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality