LeetCode 2370 - Longest Ideal Subsequence

LeetCode Problem 2370

Difficulty: 🟡 Medium
Topics: Hash Table, String, Dynamic Programming

Solution

Problem Understanding

In this problem, we are given a string s containing only lowercase English letters and an integer k. We need to find the length of the longest subsequence such that the difference between every pair of adjacent characters in that subsequence is at most k.

A subsequence does not require characters to be contiguous. We are allowed to skip characters while preserving the original order. For example, "acbd" is a subsequence of "acfgbd" because we can delete 'f' and 'g' while keeping the remaining characters in order.

The important condition is the adjacency rule inside the chosen subsequence. If two consecutive characters in the subsequence are x and y, then:

abs(ord(x) - ord(y)) <= k

This means the characters must remain close in alphabetical order. The alphabet is not cyclic, so 'a' and 'z' differ by 25, not 1.

The input constraints are large:

• 1 <= s.length <= 10^5
• 0 <= k <= 25

A string length of 100000 immediately tells us that exponential or quadratic subsequence generation approaches are impossible. We need something close to linear time.

There are several important edge cases to think about:

• When k = 0, adjacent characters in the subsequence must be identical. The answer becomes the maximum frequency of any character.
• When k = 25, every lowercase character can follow every other lowercase character, so the entire string is always valid.
• Strings with repeated characters require careful handling because the best subsequence ending with a character may improve multiple times.
• Very short strings such as length 1 should always return 1.

Approaches

Brute Force Approach

A brute force solution would generate every possible subsequence of the string and check whether each subsequence satisfies the ideal condition.

For a string of length n, there are 2^n possible subsequences. For each subsequence, we would scan adjacent characters and verify that their alphabetical difference is at most k.

This approach is correct because it explicitly checks every possible candidate and keeps the longest valid one. However, it is computationally impossible for n = 100000.

Even for n = 30, there are already more than one billion subsequences.

Key Insight for the Optimal Solution

The important observation is that we do not need to remember entire subsequences. We only need to know:

What is the best ideal subsequence ending with each character?

Since there are only 26 lowercase letters, we can maintain dynamic programming information for each letter.

Suppose we are currently processing character 'd'.

If k = 2, then 'd' can follow:

• 'b'
• 'c'
• 'd'
• 'e'
• 'f'

because their alphabetical distance from 'd' is at most 2.

So, to build the best subsequence ending in 'd', we only need the best subsequences ending in those compatible characters.

This transforms the problem into a compact dynamic programming problem with only 26 states.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n × n)	O(n)	Generates every subsequence and validates each one
Optimal Dynamic Programming	O(n × 26)	O(26)	Tracks best subsequence length ending at each character

Algorithm Walkthrough

1. Create a DP array of size 26.

Each index represents a lowercase letter:

• dp[0] represents 'a'
• dp[1] represents 'b'
• ...
• dp[25] represents 'z'

dp[i] stores the length of the longest ideal subsequence ending with that character. 2. Process the string one character at a time.

For each character char:

• Convert it into an index:

current = ord(char) - ord('a')

3. Determine which previous characters are compatible.

Any character whose index differs from current by at most k can appear immediately before the current character in an ideal subsequence.

So the valid range is:

max(0, current - k) to min(25, current + k)

4. Find the best subsequence among compatible characters.

Scan the valid range and compute:

best_previous = max(dp[i])

This gives the longest ideal subsequence that can legally transition into the current character. 5. Extend that subsequence.

The new subsequence length ending at the current character becomes:

best_previous + 1

6. Update the DP entry for the current character.

We take the maximum because the same character may appear many times in the string. 7. After processing the entire string, return the maximum value in the DP array.

Why it works

The DP array always maintains the longest valid ideal subsequence ending with each letter. When processing a new character, we consider all compatible previous ending letters and extend the best one. Since every valid ideal subsequence must end with some character, and every extension respects the adjacency constraint, the algorithm correctly builds the optimal answer incrementally.

Python Solution

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        dp = [0] * 26

        for char in s:
            current_index = ord(char) - ord('a')

            left = max(0, current_index - k)
            right = min(25, current_index + k)

            best_previous = 0

            for index in range(left, right + 1):
                best_previous = max(best_previous, dp[index])

            dp[current_index] = max(
                dp[current_index],
                best_previous + 1
            )

        return max(dp)

The implementation begins by creating a fixed-size DP array with 26 elements. Each position stores the best ideal subsequence ending with that letter.

As we iterate through the string, we convert each character into its alphabet index. This allows constant-time mapping between characters and DP positions.

For every character, we compute the compatible alphabet range using k. We then scan only those valid characters to find the best subsequence we can extend.

The expression:

best_previous + 1

represents appending the current character onto the best compatible subsequence.

We use:

max(dp[current_index], best_previous + 1)

because the same character may already have a longer subsequence from earlier processing.

Finally, the answer is the largest value stored in the DP array.

Go Solution

func longestIdealString(s string, k int) int {
	dp := make([]int, 26)

	for _, ch := range s {
		currentIndex := int(ch - 'a')

		left := currentIndex - k
		if left < 0 {
			left = 0
		}

		right := currentIndex + k
		if right > 25 {
			right = 25
		}

		bestPrevious := 0

		for i := left; i <= right; i++ {
			if dp[i] > bestPrevious {
				bestPrevious = dp[i]
			}
		}

		if bestPrevious+1 > dp[currentIndex] {
			dp[currentIndex] = bestPrevious + 1
		}
	}

	answer := 0

	for _, value := range dp {
		if value > answer {
			answer = value
		}
	}

	return answer
}

The Go implementation follows the exact same dynamic programming logic as the Python version.

A slice of length 26 stores the DP values. Since Go does not provide built-in max for integers, comparisons are handled manually with if statements.

The iteration over the string uses Go runes, but since the input contains only lowercase English letters, rune handling is straightforward and safe.

No special overflow handling is necessary because the maximum answer is at most 100000, which easily fits inside Go's int type.

Worked Examples

Example 1

Input: s = "acfgbd", k = 2

We maintain:

dp[i] = longest ideal subsequence ending with character i

Step	Character	Compatible Range	Best Previous	Updated Value
1	a	a-c	0	dp[a] = 1
2	c	a-e	1	dp[c] = 2
3	f	d-h	0	dp[f] = 1
4	g	e-i	1	dp[g] = 2
5	b	a-d	2	dp[b] = 3
6	d	b-f	3	dp[d] = 4

Final answer:

4

The longest ideal subsequence is "acbd".

Example 2

Input: s = "abcd", k = 3

Step	Character	Compatible Range	Best Previous	Updated Value
1	a	a-d	0	dp[a] = 1
2	b	a-e	1	dp[b] = 2
3	c	a-f	2	dp[c] = 3
4	d	a-g	3	dp[d] = 4

Final answer:

4

The entire string is ideal.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × 26)	For each character, we scan at most 26 letters
Space	O(26)	Fixed-size DP array

Although the time complexity is technically O(n × 26), the alphabet size is constant, so this simplifies to linear time, O(n).

The space usage is constant because the DP array always contains exactly 26 elements regardless of input size.

Test Cases

solution = Solution()

assert solution.longestIdealString("acfgbd", 2) == 4  # Example 1
assert solution.longestIdealString("abcd", 3) == 4  # Example 2

assert solution.longestIdealString("a", 0) == 1  # Single character
assert solution.longestIdealString("aaaaa", 0) == 5  # All identical characters
assert solution.longestIdealString("abcde", 0) == 1  # No differing adjacent chars allowed
assert solution.longestIdealString("abcde", 25) == 5  # Entire string always valid

assert solution.longestIdealString("az", 0) == 1  # Difference too large
assert solution.longestIdealString("az", 25) == 2  # Maximum allowed difference

assert solution.longestIdealString("edcba", 1) == 5  # Descending valid chain
assert solution.longestIdealString("leetcode", 2) >= 1  # General mixed case

assert solution.longestIdealString("abababab", 1) == 8  # Alternating compatible chars
assert solution.longestIdealString("xyzabc", 2) == 3  # Split compatibility groups

assert solution.longestIdealString("z", 25) == 1  # Single max-range character
assert solution.longestIdealString("bac", 1) == 2  # Must skip incompatible transition

Test Case Summary

Test	Why
"acfgbd", 2	Validates the main example
"abcd", 3	Entire string forms ideal subsequence
"a", 0	Smallest input size
"aaaaa", 0	Repeated identical characters
"abcde", 0	Only identical adjacent characters allowed
"abcde", 25	Maximum flexibility
"az", 0	Maximum alphabet gap invalid
"az", 25	Maximum alphabet gap valid
"edcba", 1	Descending subsequence handling
"leetcode", 2	Mixed realistic input
"abababab", 1	Frequent DP updates
"xyzabc", 2	Disconnected compatibility regions
"z", 25	Single boundary character
"bac", 1	Requires skipping characters

Edge Cases

Edge Case 1: k = 0

When k is zero, adjacent characters in the subsequence must be identical. This changes the problem into finding the most frequent character.

A naive implementation might accidentally allow transitions between different letters due to incorrect range calculations.

The implementation handles this correctly because the compatible range becomes exactly one character:

[current_index, current_index]

So only identical characters contribute to the subsequence.

Edge Case 2: k = 25

When k = 25, every lowercase letter is compatible with every other lowercase letter.

A buggy implementation might accidentally exceed array bounds when computing:

current_index + k

The solution prevents this using:

min(25, current_index + k)

This safely clamps the search range within valid alphabet indices.

Edge Case 3: Repeated Characters

Repeated characters can improve the best subsequence ending with the same letter multiple times.

For example:

s = "abababab"

The best subsequence ending with 'a' and 'b' continuously grows throughout the scan.

A common mistake is overwriting DP states incorrectly. The implementation avoids this by using:

dp[current_index] = max(
    dp[current_index],
    best_previous + 1
)

This ensures we never lose a previously better subsequence ending with the same character.