Abstract / Summary

Find the length of the longest sequence that reads the same backward as forward within a given 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 65% (1+ million submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• 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 implementation computes the length of the longest palindromic subsequence in a given string. It employs a top-down dynamic programming approach with memoization to avoid redundant calculations. The algorithm explores the relationship between the characters at the current left and right indices, recursively reducing the problem size until base conditions are reached.

Core Logic

The heart of the solution is the nested deeper function, which receives two integer parameters, left and right, representing the current substring boundaries. The function returns the length of the longest palindromic subsequence within s[left:right+1]. The recursion follows three distinct paths:

• When the left index surpasses the right index, the substring is empty, and the function returns 0.
• When the left index equals the right index, the substring consists of a single character, which is inherently a palindrome of length 1.
• When the characters at the two indices match, they can be paired as the outermost characters of a palindrome, contributing 2 to the length, and the function proceeds inward.
• When the characters differ, the function explores both possibilities of discarding either the left or the right character, taking the maximum result.

@cache
def deeper(left, right):
    if left > right:
        return 0
    if left == right:
        return 1
    if s[left] == s[right]:
        return 2 + deeper(left + 1, right - 1)
    return max(deeper(left + 1, right), deeper(left, right - 1))

The outer method simply initiates the recursion for the full string.

return deeper(0, len(s) - 1)

Edge Cases

The implementation explicitly handles two boundary conditions:

• An empty substring (left > right) yields a length of 0. This case occurs when the recursion moves past the middle of an even-length palindrome.
• A single-character substring (left == right) yields a length of 1. This case captures the central character of an odd-length palindrome and also serves as the base case for any substring that cannot be reduced further.

These conditions guarantee correct results for strings of any length, including the empty string, where the initial call becomes deeper(0, -1) and immediately returns 0.

Performance Optimizations

The primary optimization is the use of the @cache decorator from Python’s functools module. By memoizing the results of each (left, right) pair, the algorithm ensures that each distinct subproblem is solved only once. This eliminates the exponential blow-up typical of naïve recursive solutions and transforms the computation into a polynomial-time process.

Additionally, the recursion avoids unnecessary string slicing or copying; it works directly with integer indices, keeping the overhead per call minimal. The decision to return early for matching characters (2 + deeper(left + 1, right - 1)) reduces the number of recursive branches explored when a palindrome can be extended, further improving runtime efficiency.

Code Walkthrough

When longestPalindromeSubseq is invoked, the deeper function is defined and automatically wrapped with caching. The initial call deeper(0, len(s) - 1) sets the boundaries to the full string. As the recursion proceeds:

• If the outermost characters match, the algorithm counts them as part of the palindrome and recurses on the interior substring.
• If they do not match, the algorithm considers both possibilities of excluding one end, relying on the cached results to avoid recomputation.
• The recursion terminates when it reaches either an empty or single-character substring, at which point the base values propagate back up the call stack.

Through memoization, each unique pair of indices is evaluated once, and the final integer returned represents the maximum length of any palindromic subsequence that can be formed from the original string.

Imagine a long row of colorful blocks with letters written on them. A palindrome is a special sequence that reads exactly the same whether you start from the beginning or start from the very end, like a mirror image. The goal of this code is to find the longest path of blocks that forms this mirror shape.

The process happens inside a helper function that looks at two sides of a line of blocks at the same time. The labels left and right point to the blocks at the two ends. If the letter on the left side is the same as the letter on the right side, those two blocks are a perfect match for the outer part of a mirror. The code counts these two as part of the total and then steps closer to the middle to look for more matches inside.

When the letters are not the same, the code faces a fork in the road. It tries two different paths. One path skips the block on the left to see what happens next, and the other path skips the block on the right. By comparing these two trials, it picks the choice that results in the biggest pile of matching blocks.

Because looking at all those combinations can take a while, the code keeps a tiny memory of every pair it has already checked. That way, if it sees the same starting and ending spots again, it does not have to do the work twice. This continues until the markers meet in the middle and all the possible combinations have been searched to find the longest possible mirror.

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++	Java					Python			TS
	WalkCCC	C++	Java					Python
	leetcode.ca	C++	Java					Python		Go	TS
	LeetcodeHelp	C++	Java					Python
	MemoryLimitExceeded	C++						Python
	Progiez	C++	Java					Python
github	begeekmyfriend				C
	black-shadows	C++
	charles-wangkai		Java
	everthis			JS
	fartem						Ruby
	fpdjsns	C++
	fsq	C++
	gouthampradhan		Java
	haoel	C++
	JoshCrozier			JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007							Python
	MacJim	C++
	ruoru					Rust
	sonugiri1043	C++
	suxrobGM								C#
	varunu28		Java
	vli02				C
	vthwang		Java
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
begeekmyfriend	C
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
gouthampradhan	Java
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
zfang399	C++

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