Find the length of the longest subsequence where adjacent chosen characters differ by at most in alphabet position.
You are given a string s consisting of lowercase English letters and an integer k.
A subsequence of s is called ideal if for every pair of adjacent characters in the subsequence, the absolute difference between their alphabet positions is at most k.
Your task is to return the length of the longest ideal subsequence of s.
An alphabet position means a = 0, b = 1, ..., z = 25.
A subsequence keeps the original order of characters, but does not need to be contiguous.
Input Format
- A string
sof lowercase English letters. - An integer
k.
Output Format
- Return a single integer: the maximum length of an ideal subsequence.
Constraints
scontains only lowercase English letters
Example 1
Input
s = "acfgbd", k = 2
Output
4
Explanation
One longest ideal subsequence is "acbd".
atocdiffers by 2ctobdiffers by 1btoddiffers by 2 So the answer is 4.
Example 2
Input
s = "abcd", k = 3
Output
4
Explanation
All adjacent letters in the whole string differ by at most 3, so the entire string is ideal.
Show 1 more example
Example 3
Input
s = "aaaa", k = 0
Output
4
Explanation
Only equal adjacent letters are allowed when k = 0, so all four a characters can be taken.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.