NeetCode #737LC-2370Medium2-D Dynamic Programming
← Back to All Problems#737 · #2370 · Longest Ideal Subsequence(最长理想子序列)
📌 Problem Statement & Constraints
Given a lowercase string
s and an integer k, a subsequence is ideal if the alphabet distance between every two consecutive chosen characters is at most k. Return the length of the longest ideal subsequence. Constraints: 1 <= s.length <= 10^5, 0 <= k <= 25.💡 Core Algorithmic Approaches
- Let
dp[c]be the length of the longest ideal subsequence ending with the letterc. - Scanning
sleft to right, for a characterchthe best we can do is extend any subsequence whose last letter lies in[ch - k, ch + k]. - So the candidate is
1 + max(dp[c])over that window, and thendp[ch] = max(dp[ch], candidate). - The alphabet has only 26 letters, so scanning the window costs O(26) per character, giving O(26 n) = O(n).
💻 Benchmark Python3 Implementation
class Solution:
def longestIdealString(self, s: str, k: int) -> int:
dp = [0] * 26
for ch in s:
c = ord(ch) - ord("a")
lo, hi = max(0, c - k), min(25, c + k)
best = max(dp[lo:hi + 1]) + 1 # extend the best compatible ending
dp[c] = max(dp[c], best)
return max(dp)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(26 * n) = O(n): a fixed-size window scan per character.
💾 Space Complexity
O(1): 26 counters.
⚠️ Interview Pitfalls & Follow-ups
- Applying the distance to adjacent characters of
s: the constraint is on consecutive characters of the subsequence, not of the original string. - Overwriting
dp[c]instead of taking a max: a longer ending found earlier must be preserved, so usemax(dp[c], best). - Scanning all 26 letters when
kis small: the window[c-k, c+k]is tighter and clearer, though both are O(1). - Assuming the subsequence must be non-decreasing: it is a distance bound, so with large
kazmay follow ana.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.