再生题解
ty_mxzhn
·
·
题解
出题人题解。
结论：设在字符串中最近的两个相同字符的下标差为 x，则答案为 n-x。
证明：
首先答案 \ge n-x。假设相同字符为 \texttt{a}。则原字符串可以表示为 S_1\texttt{a}S_2\texttt{a}S_3。选择子序列 S_1\texttt{a}S_3 即可。
然后答案 \le n-x。这里证明稍微有点难。找到第一个两个子序列的选择在原字符串中不同的位置 p_1,p_2，则显然子序列长度 \le n-(p_2-p_1) \le n-x。