Longest Ideal Subsequence

Longest Ideal Subsequence

What is this problem about?

The Longest Ideal Subsequence problem gives you a string s consisting of lowercase letters and an integer k. Your task is to find the length of the longest subsequence where the absolute difference in the alphabetical order of any two adjacent characters is less than or equal to k. For example, if k = 2, 'a' and 'c' can be adjacent (difference is 2), but 'a' and 'd' cannot.

Why is this asked in interviews?

This question is asked to evaluate a candidate's proficiency with 1D Dynamic Programming applied to strings. It tests if you can map character constraints to array indices. It is a fantastic problem for assessing spatial optimization, as candidates who use a full 2D DP array will struggle with efficiency, whereas those who recognize the fixed alphabet size (26 letters) will breeze through it.

Algorithmic pattern used

This problem utilizes Dynamic Programming optimized with an array of fixed size. Since there are only 26 lowercase English letters, we can maintain a DP array dp[26], where dp[i] represents the length of the longest ideal subsequence ending with the i-th letter of the alphabet. As we iterate through the string, for each character, we look at the lengths of valid previous characters (within the range of -k to +k from the current character) in our DP array, find the maximum, and add 1 to it.

Example explanation

String s = "acf", k = 2. DP array of size 26, initialized to 0.

• Process 'a' (index 0): The valid range is 0 to 0+2 (a to c). The max in dp[0..2] is 0. So dp[0] = 0 + 1 = 1.
• Process 'c' (index 2): The valid range is 2-2 to 2+2 (a to e). The max in dp[0..4] is dp[0] which is 1. So dp[2] = 1 + 1 = 2.
• Process 'f' (index 5): The valid range is 5-2 to 5+2 (d to h). We check dp[3..7]. The values are all 0 (because we only have lengths for 'a' and 'c' so far). Max is 0. So dp[5] = 0 + 1 = 1.

The max value in the entire dp array is 2 (the sequence "ac"). 'f' couldn't append to 'c' because the difference is 3, which is $> k$.

Common mistakes candidates make

The biggest pitfall is using a traditional $O(N^2)$ Longest Increasing Subsequence template, comparing every character with every previous character in the string. With strings up to $10^5$ characters long, $O(N^2)$ will immediately trigger a Time Limit Exceeded error. Another common error is failing to correctly clamp the max(0, current_char - k) and min(25, current_char + k) boundaries, resulting in Array Index Out Of Bounds exceptions.

Interview preparation tip

When tackling the Longest Ideal Subsequence coding problem, recognize that the small, finite nature of the alphabet is your biggest advantage. Whenever a problem constraints the data to just 26 lowercase letters or 10 digits, it is a massive hint to use a fixed-size array of 26 or 10 to store states, dropping your inner loop from $O(N)$ to an $O(1)$ constant time check.