题解

思路

左右循环移位相等意味着对所有位置都有 $t_i=t_{i+2}$。因此好字符串只有两类：全部字符相同；或由两个不同数字交替组成，且长度必须为偶数。

问题转化为保留一个最长的上述子序列，再删除其余字符。

做法

统计每个数字的出现次数，得到周期一方案。随后枚举两个不同数字 $x,y$ 的有序对，从左到右扫描原串，依次期待 $x,y,x,y,\ldots$；遇到期待数字就选入。若最终长度为奇数，删掉最后一个字符使其变为偶数。所有方案中的最大保留长度记为 best，答案为 $|s|-best$。

正确性证明

由 $t_i=t_{i+2}$，任意好字符串的奇数位置字符相同、偶数位置字符相同。两者相同时是常值串；不同时，为使首尾循环条件成立，长度必须为偶数。算法枚举了常值数字和全部不同数字有序对。

对固定有序对，按期待字符贪心选择最早可用位置，不会使后续选择变少，故得到该模式的最长交替子序列；奇数长度最后一位无法形成好串，去掉它即为最长偶数方案。算法取全部模式最大值，因此保留字符最多，删除数最少。

复杂度分析

数字种类固定为 10，时间复杂度为 $O(100|s|)$，额外空间复杂度为 $O(1)$。

子任务说明

• $|s|\le20$ 时枚举全部子序列。
• 每串至多两种数字时只需检查唯一数字对的两个方向。
• 满数据枚举全部有序数字对。