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.
- Difficulty: Medium
- Topics: Strings, Hash Table, Dynamic Programming
- Asked at: Amazon, Google, Atlassian
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 1000000 <= k <= 25s consists of lowercase English letters.
Hints for Longest Ideal Subsequence
Hint 1
Only the last letter of the subsequence constrains what can come next — its position in the string does not.
Hint 2
So keep 26 values: the best ideal subsequence ending at each letter.
Hint 3
Appending
cextends the best of the letters withinkof 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
- Keep
dp[0 … 25], all starting at 0. - For each character
cofs, take the maximumdp[d]over|d - c| <= k. - Set
dp[c] = thatMax + 1and 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 = 0allows 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 bestJava
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