> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/lis/2370.-longest-ideal-subsequence.md).

# 2370. Longest Ideal Subsequence

this DP is similar to LIS, we only care about the tail, so I only save the last char and the freq count

```
T: O(n)
S: O(26)
```

````java
```java
class Solution {
    // 7 1 7 7 8
    // result = 1;
    // map [(1,1), (7, 3), (8, 4)]
    public int longestIdealString(String s, int k) {
        Map<Character, Integer> map = new HashMap<>();
        int result = 0;
        for (char c : s.toCharArray()) { // O(n)
            int count = 0;
            for (Character key : map.keySet()) { // O(26)
                if (Math.abs(key - c) <= k) {
                    count = Math.max(count, map.get(key));
                }
            }
            map.put(c, count+1); // 7, 1
            result = Math.max(result, count+1);
        }
        return result;
    }
}

/**
T: O(n)
S: O(26)


 t subseq in s

 abs(diff) <= k
k = 2


7 1 7 7 8

1_1

1_7

1_8

everytime update larger one



actually can use LIS idea to solve this,
but mine is also ok

這類需要限制在某範圍內的題目...邊掃邊看前面就可以, 不需要前後都看
 */
```
````