コドフォ Educational Contest 92 C Good String 解説[python]

概要

長さN の数字のみからなる文字列がある。

文字列を左回転、右回転した文字列が一致する時それは良い文字列とする時、与えられた文字列から最小で何文字削除すれば良い文字列になるかを求めよ。

ただし削除する場所は任意

考察

　実験すると、長さが奇数なら全ての文字が同じ時、良い文字列。
　長さが偶数なら偶数番目と奇数番目が同じなら良い文字列になることがわかる。

　長さ偶数を考えると、互い違いに現れる文字列で最大の長さのものをもとめたい。
　文字種が高々10種類なので、偶数番目、奇数番目の文字を固定して全探索をすると実装が楽にもとまる。

実装

import sys
import math

read = sys.stdin.buffer.read
# input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
    s = input()
    ans = 0
    for i in range(10):
        for j in range(10):
            i_bit = 0  # 0ならi かどうかを判定する
            ij_len = 0
            i_len = 0
            for k in s:
                if i_bit == 0:
                    if i == int(k):
                        i_bit = 1
                        ij_len += 1
                else:
                    if j == int(k):
                        i_bit = 0
                        ij_len += 1
                if i == int(k):
                    i_len += 1
            # print(i, j, ij_len, i_len, ans)
            ans = max(ans, i_len, (ij_len // 2) * 2)
    print(min(len(s) - 2, len(s) - ans))