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; }