843. Ideal Subsequence
A DJ is lining up a playlist labelled by the lowercase letters of s, one letter per track in the order tracks were recorded. She may drop any tracks but cannot reorder the rest. To keep the mix smooth, two tracks that end up next to each other must have letters at most k places apart in the alphabet (for example 'c' and 'f' are 3 apart; the alphabet does not wrap around).
Return the maximum number of tracks she can keep. Repeating the same letter is allowed, since its distance is 0, and a single track is always valid. Aim for time O(n * 26) and extra space O(1) (one table of 26 values).
Example 1
- Input:
- s = "gkhmjl", k = 2
- Output:
- 4
- Explanation:
Keeping g, h, j and l gives steps of 1, 2 and 2 between neighbouring letters, all within 2, and no five-letter choice works.
Example 2
- Input:
- s = "mmnoomq", k = 1
- Output:
- 5
- Explanation:
The first five letters m, m, n, o, o have neighbouring gaps of 0, 1, 1 and 0; the following m and q are too far from o.
Constraints
1 ≤ s.length ≤ 105
s consists of lowercase English letters
0 ≤ k ≤ 25
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(26 * n)
- Space
- O(1)