はまやんはまやんはまやん

hamayanhamayan's blog

空白と回文 [yukicoder No.588]

https://yukicoder.me/problems/no/588

解法

https://yukicoder.me/submissions/213892

全探索で解く。
まず、残す部分[L,R]について全探索する。
次に、残す部分を回文にするために消す文字が何個あるかをチェックする。
 
回文の判定では、範囲の前半部分が後半部分と一致するかをチェックする。
残す部分の長さM(=R-L+1)について、

  • S[L]とS[R]
  • S[L+1]とS[R-1]
  • S[L + M/2]とS[R - M/2]

を順にチェックしていき、同じなら消す必要は無く、違うならどちらも消して空白にするため、2つカウント。
a個消したとすると、残るのはM-aなので、これを最大を取ると答え。
 
計算量はオーダー的にはO(N^3)であるが、実質O(N^3/4)くらいになり、実装も軽いので通る。

string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    int N = S.length();
    
    int ans = 1;
    rep(L, 0, N) rep(R, L + 1, N) {
        int M = R - L + 1;
        int a = 0;
        rep(i, 0, M / 2) if (S[L + i] != S[R - i]) a += 2;
        ans = max(ans, M - a);
    }
    cout << ans << endl;
}