Keep the Longest Subsequence with Bounded Alphabet Gaps
Company: Infosys
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Choose a subsequence of lowercase `s` such that every two neighboring retained letters differ by at most k in ordinary alphabet position. Return its greatest possible length. Alphabet order does not wrap between a and z.
```cpp
class Solution {
public:
int longestIdealString(string s, int k);
};
```
### Examples
**Example 1:**
```text
Input: s = "azab", k = 1
Output: 3
Explanation: Keep the subsequence "aab" and skip z. Its adjacent alphabet gaps are 0 and 1.
```
**Example 2:**
```text
Input: s = "bbacb", k = 0
Output: 3
Explanation: With k equal to zero, all retained letters must match. The three b occurrences form the longest choice.
```
### Constraints
- `1 <= s.length <= 100000`.
- `0 <= k <= 25`.
- s contains lowercase English letters.
### Clarifying Questions
- Must retained characters be contiguous? No; a subsequence may skip characters while keeping their order.
- Does the alphabet wrap from `z` to `a`? No; their distance is 25.
- Which neighbors are compared? Adjacent letters in the chosen subsequence.
- What happens when `k = 0`? All retained letters must be equal.
```hint Check the boundary
Check whether skipping a character can make its two remaining neighbors compatible.
```
Overview: Find the longest subsequence whose adjacent retained letters differ by at most k alphabet positions, without wrapping the alphabet.