2370. Longest Ideal Subsequence - Explanation

1. Recursion

Intuition

An "ideal" subsequence requires that consecutive characters differ by at most k in their alphabetical positions. For each character in the string, we have two choices: skip it or include it (if it satisfies the constraint with the previous character). This decision tree naturally maps to a recursive approach where we try both options and take the maximum.

Algorithm

Define dfs(i, prev) where i is the current index and prev is the last included character (or a sentinel for none).
Base case: If i reaches the end, return 0.
Option 1: Skip the current character and recurse with dfs(i + 1, prev).
Option 2: If prev is empty or the absolute difference between current and previous character is at most k, include it with 1 + dfs(i + 1, s[i]).
Return the maximum of both options.

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        def dfs(i, prev):
            if i == len(s):
                return 0
            skip = dfs(i + 1, prev)
            include = 0
            if prev == "" or abs(ord(s[i]) - ord(prev)) <= k:
                include = 1 + dfs(i + 1, s[i])
            return max(skip, include)

        return dfs(0, "")

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution has overlapping subproblems since the same (index, previous character) pair can be reached through different paths. By caching results in a 2D table indexed by position and the previous character, we avoid redundant computation. Since there are only 26 possible previous characters (plus a "none" state), the state space is manageable.

Algorithm

Create a cache of size n x 27 (26 letters plus one for "no previous").
Convert the previous character to an index (0 to 25, or use an offset for the "none" case).
Before computing, check if the result is cached.
Compute using the same logic as plain recursion, store in cache, and return.

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        cache = [[-1] * 27 for _ in range(len(s))]

        def dfs(i, prev):
            if i == len(s):
                return 0
            if cache[i][prev + 1] != -1:
                return cache[i][prev + 1]

            skip = dfs(i + 1, prev)
            include = 0
            c = ord(s[i]) - ord('a')
            if prev == -1 or abs(c - prev) <= k:
                include = 1 + dfs(i + 1, c)
            cache[i][prev + 1] = max(skip, include)
            return cache[i][prev + 1]

        return dfs(0, -1)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up)

Intuition

We can fill a table iteratively instead of recursively. For each position i and each possible "last character" prev, we compute the longest ideal subsequence. We propagate values forward: either keep the previous state unchanged (skip current character) or extend it if the current character is within k of prev.

Algorithm

Create a 2D array dp[i][prev] of size (n+1) x 26.
For each index i from 1 to n:
- Get the current character as an index curr.
- For each prev from 0 to 25:
  - Carry forward dp[i-1][prev] to dp[i][prev].
  - If |curr - prev| <= k, update dp[i][curr] = max(dp[i][curr], 1 + dp[i-1][prev]).
Return the maximum value in dp[n].

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        dp = [[0] * 26 for _ in range(len(s) + 1)]

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

        return max(dp[len(s)])

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Dynamic Programming (Space Optimized)

Intuition

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).

Algorithm

Initialize an array dp of size 26 with zeros.
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).
Return the maximum value in dp.

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)

Time & Space Complexity

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

Common Pitfalls

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.