先设计一个 DP 检验一个给定的串 $t$ 是否合法 (当然可以直接用求 LCS 的 DP，但是这里给出的 DP 用到了 $k$ 小的性质)，然后将其 DP 数组作为状态进行计数 DP。

设 $dp[i][j]$ 表示 $t[0,i)$ 删掉 $j$ 个字符后在 $s$ 里面找子序列，至少要跳过几个字符。显然只需要考虑 $0\le j\le k$ 且 $0\le dp[i][j]\le k+1$ (值为 $k+1$ 表示无解)。并且 DP 还有单调性，即 $dp[i][j]\le dp[i][j-1]+1$。

在 $k=3$ 时，合法的状态也仅有 $200$ 多种。转移时枚举字符即可，也可以通过预处理加速。