Practice/Microsoft/Leetcode 2370. Longest Ideal Subsequence

Leetcode 2370. Longest Ideal Subsequence

CodingOptional

Problem

You are given a string s consisting of lowercase English letters and a non-negative integer k.

A valid chain is a subsequence of s where for every pair of consecutive characters in the subsequence, the absolute difference between their positions in the alphabet is at most k.

For example, if k = 2, the character 'c' can be followed by any character from 'a' to 'e' (positions differ by at most 2).

Your task is to find the length of the longest valid chain that can be formed from the string.

Requirements

1. Return an integer representing the maximum length of a valid chain
2. The chain must be a subsequence (characters maintain their relative order from the original string)
3. Adjacent characters in the chain must have alphabet positions differing by at most k
4. A single character always forms a valid chain of length 1

Constraints

• 1 ≤ s.length ≤ 105
• 0 ≤ k ≤ 25
• s consists only of lowercase English letters
• Aim for O(n × 26) or better time complexity
• Aim for O(26) or O(1) space complexity

Examples

Example 1:

` Input: s = "acfgbd", k = 2 Output: 4 Explanation: One valid chain is "acbd":

• 'a' to 'c': |0 - 2| = 2 ≤ 2 ✓
• 'c' to 'b': |2 - 1| = 1 ≤ 2 ✓
• 'b' to 'd': |1 - 3| = 2 ≤ 2 ✓ `

Example 2:

Input: s = "abcd", k = 3 Output: 4 Explanation: All characters form a valid chain since consecutive letters differ by 1.

Example 3:

Input: s = "xyz", k = 0 Output: 1 Explanation: With k=0, only identical consecutive characters are allowed, so best chain length is 1.