1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define MaxSize 5005
 6 char a[MaxSize],b[MaxSize];
 7 int dp[MaxSize];//滚动数组，相当巧妙
 8 int n;
 9 inline int max(int a,int b){
10     return a>b?a:b;
11 }
12 int lcs(){
13     int i,j,x,t;
14     memset(dp,0,sizeof(dp));
15     for(i=1;i<=n;i++){
16         x=0;//此处1
17         for(j=1;j<=n;j++)
18             if(a[i]==b[j]){
19                 t=dp[j];
20                 dp[j]=x+1;
21                 x=t;
22             }
23             else{
24                 x=dp[j];//此处2 难点~
25                 dp[j]=max(dp[j],dp[j-1]);
26             }
27     }
28     return dp[n];
29 }
30 int main(){
31     //freopen("in.txt","r",stdin);
32     while (~scanf("%d",&n)){
33         getchar();
34         scanf("%s",a+1);
35         reverse_copy(a+1,a+n+1,b+1);
36         printf("%d\n",n-lcs());
37     }
38     return 0;
39 }
40