Get started

Longest Ideal Subsequence — Medium Problem & Solution

A subsequence of s is ideal when every pair of adjacent characters in it differs by at most k in the alphabet (using plain letter positions, with no…

Problem statement

A subsequence of s is ideal when every pair of adjacent characters in it differs by at most k in the alphabet (using plain letter positions, with no wrap-around between 'z' and 'a').

Return the length of the longest ideal subsequence.

Example 1

Input: s = "acfgbd", k = 2
Output: 4
Explanation: "acbd" — the steps a→c, c→b and b→d are all within 2.

Example 2

Input: s = "abcd", k = 3
Output: 4
Explanation: The whole string qualifies.

Example 3

Input: s = "abcd", k = 0
Output: 1

Constraints

  • 1 <= s.length <= 100000
  • 0 <= k <= 25
  • s consists of lowercase English letters.

How to solve Longest Ideal Subsequence

Compress the state from 'index' down to 'last letter'. Scanning left to right, dp[c] holds the longest ideal subsequence seen so far that ends in letter c, and each new character updates exactly one entry.

Approach

  1. Keep dp[0 … 25], all starting at 0.
  2. For each character c of s, take the maximum dp[d] over |d - c| <= k.
  3. Set dp[c] = thatMax + 1 and track the overall best.

Why it works

A subsequence is extendable by c exactly when its last letter is within k of c — nothing else about it matters, so keeping only the best per last letter loses nothing. Processing the string in order guarantees that dp[d] only reflects characters strictly before the current one, which is what makes the result a genuine subsequence.

Complexity

  • Time — O(n · 26)
  • Space — O(1)

Pitfalls

  • The alphabet does not wrap: 'a' and 'z' are 25 apart, not 1.
  • The scan must be left to right, updating dp[c] only after reading the window.
  • k = 0 allows only runs of the same letter.

Reference solution

Python

def longestIdealString(s: str, k: int) -> int:
    dp = [0] * 26
    best = 0
    for ch in s:
        c = ord(ch) - 97
        lo, hi = max(0, c - k), min(25, c + k)
        cur = max(dp[lo:hi + 1])
        dp[c] = cur + 1
        best = max(best, dp[c])
    return best

JavaScript

var longestIdealString = function(s, k) {
    var dp = [];
    for (var t = 0; t < 26; t++) dp.push(0);
    var best = 0;
    for (var i = 0; i < s.length; i++) {
        var c = s.charCodeAt(i) - 97;
        var cur = 0;
        var lo = Math.max(0, c - k), hi = Math.min(25, c + k);
        for (var d = lo; d <= hi; d++) if (dp[d] > cur) cur = dp[d];
        dp[c] = cur + 1;
        if (dp[c] > best) best = dp[c];
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue