Longest Ideal Subsequence - Solution & Explanation

Problem Overview: You are given a string s and an integer k. A subsequence is considered ideal if the absolute difference between the positions of every pair of adjacent characters in the alphabet is at most k. The task is to return the length of the longest such subsequence you can build from s.

This is fundamentally a constrained subsequence problem. You want the longest chain where each new character can only extend subsequences ending with characters within a limited alphabet distance. The constraint ties the problem directly to dynamic programming over characters.

Approach 1: Dynamic Programming with Character Indexing (Time: O(n * 26), Space: O(26))

Track the best subsequence length that ends with each letter of the alphabet. Maintain an array dp[26] where dp[i] stores the longest ideal subsequence ending with character ('a' + i). Iterate through the string and map each character to its alphabet index.

For the current character c, check all characters within the valid range [c - k, c + k]. The maximum value among those entries represents the best subsequence that can be extended. Update dp[c] to max(dp[c], best + 1). Since the alphabet size is fixed at 26, the inner scan is constant time. This keeps the algorithm linear with respect to the string length.

This approach works well because it converts a subsequence dependency into a small state transition over the alphabet. Instead of tracking subsequences for every index, you only store the best result per character. The idea is a classic pattern in string problems that combine ordering constraints with limited character sets.

Approach 2: Optimized Use of HashMap (Time: O(n * 26), Space: O(26))

This variant replaces the fixed array with a HashMap or dictionary keyed by characters. For each character in the string, check all characters whose alphabet distance is within k. Look up their current best subsequence length in the map and compute the best extension.

Update the map entry for the current character with the new maximum length. Conceptually the algorithm is identical to the array approach, but the map structure makes the implementation flexible when the character domain is not strictly limited or when the language favors dictionary-style lookups.

The main operations are hash lookups and updates, which remain constant time on average. This pattern frequently appears in problems involving character transitions and frequency tracking, making it closely related to techniques used in hash table based dynamic programming.

Recommended for interviews: The array-based dynamic programming approach is what most interviewers expect. It shows that you recognize the small fixed alphabet and compress the DP state into 26 buckets instead of tracking every subsequence explicitly. A brute-force subsequence search would be exponential and impractical. The optimized DP demonstrates strong pattern recognition and the ability to reduce a problem to constant-sized state transitions.