#2370

Longest Ideal Subsequence

specialist · 920 · lc medium +32 · verified · 46.6% accepted · 1,530 likes · top 31%

Description

A string t is ideal with respect to string s and integer k when:

- t is a subsequence of s.

- Every pair of adjacent characters in t differs by at most k positions in the alphabet.

Return the length of the longest ideal subsequence of s.

Note: alphabet distances are not cyclic — 'a' and 'z' differ by 25.

Example 1:

Input: s = "acfgbd", k = 2

Output: 4

Explanation: The longest ideal string is "acbd". The length of this string is 4, so 4 is returned.

Note that "acfgbd" is not ideal because 'c' and 'f' have a difference of 3 in alphabet order.

Example 2:

Input: s = "abcd", k = 3

Output: 4

Explanation: The longest ideal string is "abcd". The length of this string is 4, so 4 is returned.

Code

1

2

3

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:

class Solution:
    def longestIdealString(self, s: str, k: int) -> int: