Abstract / Summary

Find the longest subsequence where no two chosen elements have a difference equal to a given value.

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 47% (200k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Hash Table
• 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 a method that computes the length of the longest ideal subsequence within a given lowercase alphabetic string s. An ideal subsequence is defined such that the absolute difference between the alphabetical indices of any two consecutive characters does not exceed the integer k. The algorithm processes the input string in a single pass while maintaining a compact dynamic-programming table that records the best achievable length ending with each letter.

Key Steps

Allocation of the DP table

chain = [0] * 26

A fixed-size list of length 26 is created, one entry for each letter of the English alphabet. Each entry will hold the length of the longest ideal subsequence that terminates with the corresponding character.

Traversal of the input string

for c in s:

The method iterates over every character c in the input string s. This sequential scan guarantees that the subsequence respects the original order of characters.

Mapping a character to its alphabet index and computing the admissible window

id    = ord(c) - ord("a")
left  = max(0, id - k)
right = min(25, id + k)

The character c is converted to a zero-based index id. The variables left and right define the inclusive range of alphabet indices that are allowed to precede c in an ideal subsequence, bounded by the limits of the alphabet (0 and 25). The use of max and min ensures that the window never exceeds the array bounds, correctly handling characters at the extremes of the alphabet.

Updating the DP entry for the current character

chain[id] = 1 + max(chain[left : right + 1])

The algorithm looks up the maximum subsequence length among all permissible predecessor letters (chain[left : right + 1]). Adding one accounts for the inclusion of the current character, and the result is stored back into chain[id]. This step embodies the core dynamic-programming transition.

Extracting the final answer

return max(chain)

After processing the entire string, the longest ideal subsequence may end with any letter. Taking the maximum over the chain array yields the required length.

Edge Cases Handled

When the input string s is empty, the loop body never executes, leaving the chain array filled with zeros. The final max(chain) therefore returns zero, correctly indicating that no subsequence exists.

If k is larger than the size of the alphabet (for example, k >= 25), the computed left and right values are clamped to the full range [0, 25]. Consequently, every previously seen character becomes a valid predecessor, and the algorithm gracefully degrades to computing the length of the longest non-decreasing subsequence in terms of alphabetical order.

Characters at the beginning ('a') or end ('z') of the alphabet generate windows that would otherwise extend beyond the array limits. The max and min guards prevent out-of-range slicing, ensuring that the slice operation always receives a valid range.

Performance Optimizations

The implementation relies on a constant-size array (chain) rather than a dictionary or hash map, which eliminates the overhead of dynamic key lookups and provides direct index access.

The slice chain[left : right + 1] extracts only the relevant segment of the DP table for each character, and the built-in max function operates on this small, bounded slice. Because the slice length never exceeds 2k + 1 (capped at 26), the per-character work remains bounded and independent of the input length.

By updating the DP entry in place (chain[id] = …) the algorithm avoids the creation of auxiliary structures for each iteration, reducing memory churn and improving cache locality.

Overall, the design leverages the limited alphabet size to keep both time and space usage tightly constrained while still delivering the correct result for all valid inputs.

Imagine building a tall tower out of alphabet blocks. There are twenty-six spots on the shelf, one for each letter from a to z, which starts out completely empty. When a new letter block appears, look at the shelf to see how many blocks are already stacked where the neighbors are. Because the rule says letters must be close together, focus only on the neighbors that are within a short distance of the new letter. Find the tallest stack among those nearby neighbors and place the new block right on top of that one to make the stack even higher. Do this for every single letter in the line, checking the shelf each time to see where the best place is to grow the tallest tower possible. By the end, the tallest stack of blocks represents the longest path found.

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

not analyzed yet

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	Python		C++	Java		TS
	WalkCCC	Python		C++	Java
	leetcode.ca	Python		C++	Java	Go	TS
	Progiez	Python		C++	Java
github	charles-wangkai				Java
	everthis		JS
	fsq			C++
	JoshCrozier		JS
	lkwq007	Python
	trung-hn	Python
	wisdompeak			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
trung-hn	Python
wisdompeak	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