#undef DEBUG #ifdef DEBUG #define debug(...) fprintf(stderr, __VA_ARGS__) #else #define debug(...) do ; while(0) #define NDEBUG #endif #include <assert.h> #include <stdbool.h> #include <stdio.h> #include <algorithm> using namespace std; int main () { #ifdef CONTEST freopen("palseq.in", "rt", stdin); freopen("palseq.out", "wt", stdout); #endif // input int N; scanf("%d\n", &N); char s[N+1]; for (int i=0; i<N; i++) s[i] = getchar(); s[N] = '\0'; // solve, dp: f[N+1][N] but I only need 3 lines int f[3][N]; /* f[n][i] = the least number of characters that must be erased from the segment starting at i and has length n, so that what remains is a palindome. */ for (int i=0; i<N; i++) f[0][i] = f[1][i] = 0; for (int n=2; n<=N; n++) for (int i=0; i<=N-n; i++) if (s[i] == s[i+n-1]) f[n%3][i] = f[(n-2)%3][i+1]; else f[n%3][i] = 1 + min(f[(n-1)%3][i], f[(n-1)%3][i+1]); // answer printf("%d\n", f[N%3][0]); return 0; }