Problem

You are given a string s consisting of lowercase letters and an integer k. We call a string t ideal if the following conditions are satisfied:

  • t is a subsequence of the string s.
  • The absolute difference in the alphabet order of every two adjacent letters in t is less than or equal to k.

Return the length of thelongest ideal string.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Note that the alphabet order is not cyclic. For example, the absolute difference in the alphabet order of 'a' and 'z' is 25, not 1.

Examples

Example 1

1
2
3
4
5
6
7


    
    
    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

1
2
3
4
5
6
7


    
    
    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.

Constraints

  • 1 <= s.length <= 10^5
  • 0 <= k <= 25
  • s consists of lowercase English letters.

Solution

Method 1 – Dynamic Programming with Character State (1)

Intuition

We use dynamic programming to keep track of the longest ideal subsequence ending with each character. For each character in the string, we look at all possible previous characters within the allowed difference and update the dp state.

Approach

  1. Initialize a dp array of size 26 (for each lowercase letter) to store the length of the longest ideal subsequence ending with each character.
  2. For each character in the string:
    • For all characters within distance k in the alphabet, update the dp value for the current character.
  3. The answer is the maximum value in the dp array after processing the string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int longestIdealString(string s, int k) {
        vector<int> dp(26, 0);
        int ans = 0;
        for (char c : s) {
            int idx = c - 'a';
            int best = 0;
            for (int j = max(0, idx - k); j <= min(25, idx + k); ++j) {
                best = max(best, dp[j]);
            }
            dp[idx] = best + 1;
            ans = max(ans, dp[idx]);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func longestIdealString(s string, k int) int {
    dp := make([]int, 26)
    ans := 0
    for _, c := range s {
        idx := int(c - 'a')
        best := 0
        for j := max(0, idx-k); j <= min(25, idx+k); j++ {
            if dp[j] > best {
                best = dp[j]
            }
        }
        dp[idx] = best + 1
        if dp[idx] > ans {
            ans = dp[idx]
        }
    }
    return ans
}
func max(a, b int) int { if a > b { return a }; return b }
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int longestIdealString(String s, int k) {
        int[] dp = new int[26];
        int ans = 0;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            int best = 0;
            for (int j = Math.max(0, idx - k); j <= Math.min(25, idx + k); j++) {
                best = Math.max(best, dp[j]);
            }
            dp[idx] = best + 1;
            ans = Math.max(ans, dp[idx]);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun longestIdealString(s: String, k: Int): Int {
        val dp = IntArray(26)
        var ans = 0
        for (c in s) {
            val idx = c - 'a'
            var best = 0
            for (j in maxOf(0, idx - k)..minOf(25, idx + k)) {
                best = maxOf(best, dp[j])
            }
            dp[idx] = best + 1
            ans = maxOf(ans, dp[idx])
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        dp = [0] * 26
        ans = 0
        for c in s:
            idx = ord(c) - ord('a')
            best = 0
            for j in range(max(0, idx - k), min(25, idx + k) + 1):
                best = max(best, dp[j])
            dp[idx] = best + 1
            ans = max(ans, dp[idx])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn longest_ideal_string(s: String, k: i32) -> i32 {
        let mut dp = vec![0; 26];
        let mut ans = 0;
        for c in s.chars() {
            let idx = (c as u8 - b'a') as usize;
            let mut best = 0;
            for j in idx.saturating_sub(k as usize)..=usize::min(25, idx + k as usize) {
                best = best.max(dp[j]);
            }
            dp[idx] = best + 1;
            ans = ans.max(dp[idx]);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    longestIdealString(s: string, k: number): number {
        const dp = Array(26).fill(0);
        let ans = 0;
        for (const c of s) {
            const idx = c.charCodeAt(0) - 97;
            let best = 0;
            for (let j = Math.max(0, idx - k); j <= Math.min(25, idx + k); j++) {
                best = Math.max(best, dp[j]);
            }
            dp[idx] = best + 1;
            ans = Math.max(ans, dp[idx]);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(nk), where n is the length of s and k is the allowed difference. For each character, we check up to 2k+1 states.
  • 🧺 Space complexity: O(1), since the dp array is always of size 26.