this DP is similar to LIS, we only care about the tail, so I only save the last char and the freq count
```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
้้ก้่ฆ้ๅถๅจๆ็ฏๅๅ
ง็้ก็ฎ...้ๆ้็ๅ้ขๅฐฑๅฏไปฅ, ไธ้่ฆๅๅพ้ฝ็
*/
```