Longest Ideal Subsequence

medium dynamic programming string hash table

Problem

Given a lowercase string s and an integer k, a string t is ideal if it is a subsequence of s and the absolute alphabet-order difference of every two adjacent letters in t is at most k. Return the length of the longest ideal string. The alphabet is not cyclic, so the gap between 'a' and 'z' is 25.

Inputs = "acfgbd", k = 2

Output4

The longest ideal string is "acbd" (length 4). "acfgbd" itself fails because 'c' and 'f' differ by 3 > 2.

s (lowercase letters)

k (0..25)

def longestIdealString(s, k):
    dp = [0] * 26                       # dp[c] = best ideal subseq ending in letter c
    for ch in s:
        cur = ord(ch) - ord('a')
        best = 0
        lo, hi = max(0, cur - k), min(25, cur + k)
        for prev in range(lo, hi + 1):  # any letter within distance k
            if dp[prev] > best:
                best = dp[prev]
        dp[cur] = best + 1              # extend the best compatible run
    return max(dp)

function longestIdealString(s, k) {
  const dp = new Array(26).fill(0);     // dp[c] = best ideal subseq ending in letter c
  for (const ch of s) {
    const cur = ch.charCodeAt(0) - 97;
    let best = 0;
    const lo = Math.max(0, cur - k), hi = Math.min(25, cur + k);
    for (let prev = lo; prev <= hi; prev++) { // any letter within distance k
      if (dp[prev] > best) best = dp[prev];
    }
    dp[cur] = best + 1;                  // extend the best compatible run
  }
  return Math.max(...dp);
}

int longestIdealString(String s, int k) {
    int[] dp = new int[26];             // dp[c] = best ideal subseq ending in letter c
    int ans = 0;
    for (char ch : s.toCharArray()) {
        int cur = ch - 'a';
        int best = 0;
        int lo = Math.max(0, cur - k), hi = Math.min(25, cur + k);
        for (int prev = lo; prev <= hi; prev++) { // any letter within distance k
            if (dp[prev] > best) best = dp[prev];
        }
        dp[cur] = best + 1;             // extend the best compatible run
        ans = Math.max(ans, dp[cur]);
    }
    return ans;
}

int longestIdealString(string s, int k) {
    vector<int> dp(26, 0);              // dp[c] = best ideal subseq ending in letter c
    int ans = 0;
    for (char ch : s) {
        int cur = ch - 'a';
        int best = 0;
        int lo = max(0, cur - k), hi = min(25, cur + k);
        for (int prev = lo; prev <= hi; prev++) { // any letter within distance k
            if (dp[prev] > best) best = dp[prev];
        }
        dp[cur] = best + 1;             // extend the best compatible run
        ans = max(ans, dp[cur]);
    }
    return ans;
}

Explanation

The trick is to define the DP by the last letter rather than by string position. Let dp[c] be the length of the longest ideal subsequence we can build so far that ends with the letter c (one of the 26 lowercase letters).

We scan s left to right. When we reach a character with letter index cur, any subsequence ending in cur can be formed by appending this character to a previous subsequence that ended in a compatible letter — one whose index is within k of cur, i.e. in the window [cur−k, cur+k] (clamped to 0..25).

So we take the best dp value over that window, add 1 for the current character, and store it as the new dp[cur]. Because we process characters in order, every value we read from the window already represents a valid subsequence that appears earlier in the string, which keeps the subsequence order correct.

Only 26 states exist, and each character scans a window of at most 2k+1 ≤ 51 letters, so the work per character is constant. The answer is the maximum entry of dp after the whole scan.

Example: s = "acbd", k = 2 survives because adjacent gaps are |a−c|=2, |c−b|=1, |b−d|=2, all ≤ 2; the full "acfgbd" fails at 'c'→'f' (gap 3).

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