Longest Ideal Subsequence

How it works

Since we only need to know the longest subsequence ending at each character, we can use a single array of size 26. For each character in the string, we look at all characters within distance k and take the maximum length, then update the entry for the current character. This reduces space from O(n) to O(1) (constant 26 entries).

Steps

1. Initialize an array dp of size 26 with zeros.
2. For each character c in the string:
   • Convert c to index curr.
   • Find the maximum value in dp[prev] for all prev where |curr - prev| <= k.
   • Set dp[curr] = max(dp[curr], 1 + maxFound).
3. Return the maximum value in dp.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) since we have at most 26 different characters.

Things to watch for

Confusing Subsequence with Substring

A subsequence does not require elements to be contiguous in the original string. Some solutions incorrectly enforce that characters must be adjacent in the input, which is the definition of a substring. Remember that you can skip characters while maintaining relative order.

Off-by-One Errors in Character Distance Calculation

When checking if the difference between two characters is at most k, ensure you use the absolute value of the difference between their positions in the alphabet. A common mistake is comparing ASCII values directly without converting to 0-indexed positions, or forgetting to take the absolute value when the current character is alphabetically before the previous one.

Not Considering All Valid Previous Characters

When computing the longest subsequence ending at a character, you must consider all previous characters within distance k, not just the immediately preceding one in the string. The optimal extension might come from any character in the range [curr - k, curr + k], and failing to check the entire range leads to suboptimal answers.

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

        for c in s:
            curr = ord(c) - ord('a')
            longest = 1
            for prev in range(26):
                if abs(curr - prev) <= k:
                    longest = max(longest, 1 + dp[prev])
            dp[curr] = max(dp[curr], longest)

        return max(dp)

class Solution {
public:
    int longestIdealString(string s, int k) {
        vector<int> dp(26, 0);

        for (char c : s) {
            int curr = c - 'a';
            int longest = 1;
            for (int prev = 0; prev < 26; prev++) {
                if (abs(curr - prev) <= k) {
                    longest = max(longest, 1 + dp[prev]);
                }
            }
            dp[curr] = max(dp[curr], longest);
        }

        return *max_element(dp.begin(), dp.end());
    }
};