字母交换------区间DP

【编码题】
字符串S由小写字母构成，长度为n。定义一种操作，每次都可以挑选字符串中任意的两个相邻字母进行交换。询问在至多交换m次之后，字符串中最多有多少个连续的位置上的字母相同？

根据题意，我们要求一个字符串经过m次交换后其包含的最长连续子串。其最长连续字串中的字母可能是从a~z之间的任意一个，我们可以按照字母进行遍历，取最大值即可。
故，我们首先统计中不同字母在原字符串中的位置。例如：abbcaca中,字符a所在的位置为0,4,6；字符b所在的位置为1，2；字符c所在的位置为3,5.
拿字符a举例，我们要将字符a组成长度为3的最长连续子串至少需要多少次交换呢？如果交换次数大于m,就说明不行。故我们要从小区间往大区间去遍历，如果最后得到的结果大于等于m则要舍弃。
我们设dp[i][j]为将pos[i]~pos[j]中的字符组成连续字串需要的交换次数。有如下递推公式：
dp[i][j] = dp[i+1][j-1]+(pos[j]-pos1[j-1]-1)+(pos1[i+1]-pos[i]-1)，其中pos[j-1]-pos[i+1] = (j-i-2)
dp[i][j] = dp[i+1][j-1] - (j-i)

import java.util.Scanner;

public class T3 {
        public static void main(String[] args) {
                Scanner scanner = new Scanner(System.in);
                String s = scanner.next();
                int m = scanner.nextInt();
                int ans = 1;
                for(char c = 'a' ; c<='z' ; c++){
                        int[] pos = new int[s.length()];
                        int cnt = 0;
                        for(int i = 0 ; i<s.length();i++){
                                if(s.charAt(i) == c){
                                       pos[cnt] = i;
                                       cnt++;
                                }
                        }
                        //只有一个字符，最多为1次
                        if(cnt<2)
                                continue;

                        int[][] dp = new int[cnt][cnt];
                        for(int i = 0 ;i<cnt;i++){
                                for(int j = 0;j<cnt;j++)
                                        dp[i][j]=0;
                        }
                        int tem = 1;
                        for(int len  = 2 ;len<=cnt;len++){
                                for(int i = 0 ;i+len-1<cnt;i++){
                                        dp[i][i+len-1] = dp[i+1][i+len-2] + pos[i+len-1] - pos[i] - len+1;
                                        if(dp[i][i+len-1]<=m)
                                                tem = len;
                                }
                        }
                        ans = Math.max(ans,tem);
                }
                System.out.println(ans);
        }
}