# 2370. Longest Ideal Subsequence
###### tags: `Leetcode` `Medium` `Greedy` `State Machine` `Dynamic Programming`
Link: https://leetcode.com/problems/longest-ideal-subsequence/description/
## 思路
首先想到这道题和longest increasing subsequence差不多
只不过在遍历的时候不再是看value小于curr value的那些```j```
我们需要找到距离curr character小于等于```k```的character的index
因此我们只需要用一个```prev[]```记录前面出现过哪些character 以及他们**最后**出现的位置
因为例如```s[i]='c', s[j]='c', i>j```, 那么```dp[j]>=dp[i]```
## Code

class Solution {
    public int longestIdealString(String s, int k) {
        int n = s.length();
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int[] prev = new int[26];
        Arrays.fill(prev, -1);
        
        int ans = 1;
        for(int i=0; i<n; i++){
            int idx = s.charAt(i)-'a';
            for(int j=Math.max(0, idx-k); j<=Math.min(25, idx+k); j++){
                if(prev[j]!=-1){
                    dp[i] = Math.max(dp[prev[j]]+1, dp[i]);
                    ans = Math.max(ans, dp[i]);
                }
            }
            prev[idx] = i;
        }
        return ans;
    }
}