Longest Ideal String

medium dp string

Problem

You are given a string s of lowercase letters and an integer k. A subsequence of s is called ideal if every pair of adjacent characters in it sits at most k positions apart in the alphabet (no wraparound, so 'a' and 'z' are 25 apart). Return the length of the longest ideal subsequence.

Inputs = "acfgbd", k = 2

Output4

"acbd" is ideal: the adjacent alphabet gaps are 2, 1 and 2, all within k = 2, and no longer ideal subsequence exists.

s (lowercase letters, max 16)

k (0..25)

def longest_ideal_string(s, k):
    dp = [0] * 26   # dp[c] = longest ideal subsequence ending with letter c
    for ch in s:
        c = ord(ch) - ord('a')
        lo = max(0, c - k)
        hi = min(25, c + k)
        best = 0
        for j in range(lo, hi + 1):
            best = max(best, dp[j])
        dp[c] = best + 1
    return max(dp)

function longestIdealString(s, k) {
  const dp = new Array(26).fill(0); // dp[c] = best ending with letter c
  for (const ch of s) {
    const c = ch.charCodeAt(0) - 97;
    const lo = Math.max(0, c - k);
    const hi = Math.min(25, c + k);
    let best = 0;
    for (let j = lo; j <= hi; j++) best = Math.max(best, dp[j]);
    dp[c] = best + 1;
  }
  return Math.max.apply(null, dp);
}

int longestIdealString(String s, int k) {
    int[] dp = new int[26]; // dp[c] = best ending with letter c
    for (char ch : s.toCharArray()) {
        int c = ch - 'a';
        int lo = Math.max(0, c - k);
        int hi = Math.min(25, c + k);
        int best = 0;
        for (int j = lo; j <= hi; j++) best = Math.max(best, dp[j]);
        dp[c] = best + 1;
    }
    int ans = 0;
    for (int v : dp) ans = Math.max(ans, v);
    return ans;
}

int longestIdealString(string s, int k) {
    vector<int> dp(26, 0); // dp[c] = best ending with letter c
    for (char ch : s) {
        int c = ch - 'a';
        int lo = max(0, c - k);
        int hi = min(25, c + k);
        int best = 0;
        for (int j = lo; j <= hi; j++) best = max(best, dp[j]);
        dp[c] = best + 1;
    }
    return *max_element(dp.begin(), dp.end());
}

Explanation

The key insight is that an ideal subsequence is fully described by one thing: the letter it ends with. Whatever came before, only the last letter constrains what we may append next. So instead of a DP indexed by position, we keep just 26 numbers: dp[c] = the length of the longest ideal subsequence seen so far that ends with letter c.

We scan s left to right. For the current character c, any subsequence it extends must end with a letter within k alphabet positions of c, i.e. a letter in the window [c−k, c+k] (clamped to a..z). We take the best value in that window of at most 2k + 1 cells and set dp[c] = best + 1. Appending c to the longest valid predecessor is always optimal, so this greedy-looking update is a correct DP transition.

Walking through s = "acfgbd", k = 2: 'a' starts a chain (dp[a] = 1); 'c' sees dp[a] inside its window [a..e], so dp[c] = 2; 'f' only reaches [d..h], which excludes both a and c, so it starts fresh with dp[f] = 1; 'g' reaches dp[f] and becomes 2; 'b' sees dp[a] = 1 and dp[c] = 2 in [a..d], takes the larger, and becomes 3; finally 'd' sees dp[b] = 3 in [b..f] and becomes 4. The answer is the maximum cell, 4, matching the subsequence "acbd".

Note the alphabet does not wrap: 'a' and 'z' are 25 apart, never adjacent-friendly for small k. That is why a simple clamped window over a flat 26-cell array is all we need.

Each of the n characters scans a window of at most 2k + 1 ≤ 26 cells, so the time is O(n · k), effectively linear, and the state is a constant 26 integers, so space is O(26).

Time: O(n · k) Space: O(26)