文字列 $t$ が与えられるので、$t$ の循環左シフト後と循環右シフト後の文字列を等しくしたい。 $t$からいくつか文字を取り除いてこの条件を満たすときに、取り除く最小の文字数は？
$n$ を $t$ の文字列長として、その偶奇で分けて考える。
$n$ が奇数の場合
$t = t_1 t_2 t_3 t_4 t_5$ を例とする。 巡回左シフト $ t_2 t_3 t_4 t_5 t_1$ と巡回右シフト $t_5 t_1 t_2 t_3 t_4$ を等しくしたい。 つまり、すべての文字を等しくする必要がある。
$n$ が偶数の場合
$t = t_1 t_2 t_3 t_4$ を例とする。 巡回左シフト $t_2 t_3 t_4 t_1$ と巡回右シフト $t_4 t_1 t_2 t_3$ を等しくしたい。 つまり、偶数番目はすべて同じ文字であって、かつ奇数番目もすべて同じ文字でないといけない。
解法
いくつかの文字を取り除いた後の文字列の先頭2文字について全探索をする。 先頭2文字が同じ場合、先頭2文字$aa$の後に何文字か$a \dots a$が続けばよい。 違う場合は、先頭2文字$ab$の後に$ababab \dots ab$が続けばよい。