题解：字符串DP

定义$f[i][j]$$表示前$i$个字母以字母$$j$结尾的最长子序列长度

对于前$i$个字母

• 如果不选择第$i$个字母，则对于任意$0\le j\le 2$，都有$f[i][j]=f[i-1][j]$
• 如果选择第$i$个字母，先把当前字母映射到$[0,25]$(x=s[i]-'a')，然后开始枚举所有$x-k\le j \le x+k$

更新$f[i][x]=max(f[i][x],f[i-1][j]+1)$

题目内容

给定一个只含小写字母的字符串$s$ , $k$阶完美子序列$t$的定义是：$t$是字符串$s$ 的一个子序列.并且$t$中任意一个相邻的字符在字符表中距离相差不过$k$.现在塔子哥需要你求出最长的k阶完美子序列

说明：

​ 1.字符串的子序列同样是一个字符串，并且子序列还满足:可以经由字符串删除某些字符(也可以不删除)但不改变剩余字符的顺序得到。

​ 2.字符表的距离是不循环的，即$a$ 和 $z$ 的距离是$25$ 而不是$1$

输入描述

每行输入一个字符串$s$和一个整数$k$

$|s| \leq 10^5 , 0 \leq k \leq 25$

输出描述

输出为整数$n$，代表字符串$s$的最长$k$阶完美字符串长度

示例1

输入

bcda 1

输出

3

说明：bcd是一个合法的最长序列,长度为3

示例2

输入

abbccd 0

输出

2

说明：bb/cc是一个合法的最长序列.长度为2