⚡Flashcard Drill➔
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

  1. Let dp[c] be the length of the longest ideal subsequence ending with the letter c.
  2. Scanning s left to right, for a character ch the best we can do is extend any subsequence whose last letter lies in [ch - k, ch + k].
  3. So the candidate is 1 + max(dp[c]) over that window, and then dp[ch] = max(dp[ch], candidate).
  4. 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 use max(dp[c], best).
  • Scanning all 26 letters when k is 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 k a z may follow an a.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems