对于 $m\ge3$ 可以从前往后贪心构造，考虑当前 $a'$ 与 $1\sim m$ 的 $\text{LCS}$ 为 $s$，则任意时刻 $s<m$。当 $s\leq m-2$ 时可以任意转移后继到 $0,1,s+1$；当 $s=m-1$ 时如果接上 $m$ 就是非法的，考虑删除 $m-1$ 这样转移到 $s=0$ 但代价 $+1$。$dp_{i,c,s}$ 表示填完前 $i$ 个 $\text{LCS}=s$，代价为 $c$。而 $c\leq \frac nm,s\in[0,m)$ 所以状态数是 $O(n\times \frac nm\times m)=O(n^2)$，转移是 $O(1)$ 的。

对于 $m=2$，考虑将原串看成括号序列，则 $>2$ 的数必须被保留并分割剩下的部分。$1$ 看成 ( 而 $2$ 看成 ) 就要求不能存在相邻的 ()，最终形如 ))))((((。考虑代价的下界是 $\min(occ_1,occ_2)$。可以发现当原串为合法括号序列时一定取到这个下界，并且自由留成全 $1$ 或全 $2$。将任意的括号序列写成 $S_0)S_1)S_2)\cdots)S_k(S_{k+1}(\cdots(S_m$ 的形式，其中 $S$ 代表一个合法括号序列。那么最终这个串要删除的就是所有 $S$ 长度的总和。

考虑固定 $k$ 对删除得到总长 $2k$ 的合法括号序列 $S'$，那么就是往 $n-2k$ 的最终串里面插。最终串不包含相邻 $1,2$，可以递推得到长度为 $l$ 的最终串方案数 $f_l=kf_{l-1}-f_{l-2}$。对于总长 $S'$ 还需要分入 $n-2k+1$ 个盒子，这个是卡特兰数自卷积，经典的双射是在前面加 $n-2k+1$ 个 (，和它配对的 ) 中间的部分就是一个盒子对应的序列。那么这个的计数就是单直线反射容斥，预处理组合数后可以 $O(1)$ 算。

对 $m\ge 3$ 时间复杂度 $O(n^2)$，对 $m=2$ 时间复杂度 $O(n)$。