Longest Ideal Subsequence

Medium
875.

Longest Ideal Subsequence

Longest Ideal Subsequence is a medium coding problem on strings, hash table and dynamic programming, asked in Amazon, Google and Atlassian interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestIdealString = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Ideal Subsequence — Solution in Python, Java & C++

Longest Ideal Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Longest Ideal Subsequence is a medium coding problem on strings, hash table and dynamic programming, asked in Amazon, Google and Atlassian interviews.

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.

Hints for Longest Ideal Subsequence

  1. Hint 1

    Only the last letter of the subsequence constrains what can come next — its position in the string does not.

  2. Hint 2

    So keep 26 values: the best ideal subsequence ending at each letter.

  3. Hint 3

    Appending c extends the best of the letters within k of it.

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

Java

public static int longestIdealString(String s, int k) {
    int[] dp = new int[26];
    int best = 0;
    for (int i = 0; i < s.length(); i++) {
        int c = s.charAt(i) - 'a';
        int cur = 0;
        for (int d = Math.max(0, c - k); d <= Math.min(25, c + k); d++) {
            cur = Math.max(cur, dp[d]);
        }
        dp[c] = cur + 1;
        best = Math.max(best, dp[c]);
    }
    return best;
}

C++

int longestIdealString(string s, int k) {
    vector<int> dp(26, 0);
    int best = 0;
    for (char ch : s) {
        int c = ch - 'a';
        int cur = 0;
        for (int d = max(0, c - k); d <= min(25, c + k); d++) cur = max(cur, dp[d]);
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets