字母交换

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strs = sc.nextLine().split(" ");
        String s = strs[0];
        int count = Integer.parseInt(strs[1]);
        int len = s.length();
        int[][] record = new int[len][26]; //记录字符串s的每个位置和26个字母的关系
        int[] length = new int[26]; //记录每个字母在规定交换次数内最长的相同字母数量
        for(int i = 0; i < len; i++){
            record[i][s.charAt(i)-'a'] = 1;
        }
        for(int i = 0; i < 26; i++){
            int[] position = new int[len]; //对于每个字母，记录字符串s中出现该字母的位置
            int k = 0; //字符串s中出现该字母k次
            for(int j = 0; j < len; j++){
                if(record[j][i] == 1){
                    position[k] = j;
                    k += 1;
                }
            }
            if(k == 0){
                length[i] = 0;
            }else if(k == 1){
                length[i] = 1;
            }else{
                int answer = Integer.MIN_VALUE;
                for (int p = 0; p < k; p++){
                    for (int q = p+1; q < k; q++){
                        int res = dfsSwichCharacter(p, q, position);
                        if(res <= count){ //在规定交换次数内，更新连续的某个相同字母数量
                            answer = Math.max(answer, q-p+1);
                        }
                    }
                }
                length[i] = answer;
            }
        }
        int result = Integer.MIN_VALUE;
        for(int i : length){
            result = Math.max(result, i);
        }
        System.out.println(result);
    }
    
    public static int dfsSwichCharacter(int i, int j, int[] position){
        if(i == j){
            return 0;
        }else if(i+1 == j){ //说明字符串s中position[i]和position[j]之间不可能再有该字母，所以移动次数就是坐标之差减一
            return position[j] - position[i] - 1;
        }else{ //移动次数相当于是把position[j]的字母移到position[i]隔壁的次数减去这两个位置之间该字母的个数
            return dfsSwichCharacter(i+1, j-1, position) + position[j]-position[i]-1 - (j-i-1);
        }
    }
}

// Java

	public static void solv(String s, int m){



	    Map<Character, List> map = new HashMap<>(26);



	    for (int i = 0; i < s.length(); i++){



	        char c = s.charAt(i);



	        List list = map.get(c);



	        if (list == null)



	            map.put(c, list = new ArrayList<Integer>(100));



	        list.add(i);



	    }



	    int maxLen = 1;



	    for (Map.Entry<Character, List> entry : map.entrySet()){



	        List<Integer> arrayList = entry.getValue();



	        for (int i = 0; i < arrayList.size(); i++){



	            int ctr = arrayList.get(i);



	            int []move = new int[arrayList.size()];



	            // 获取 move[]，表示每个相同字母到中心点 ctr 需要移动的最少步数



	            for (int j = 0; j < arrayList.size(); j++)



	                move[j] = (Math.abs(arrayList.get(j) - ctr) -



	                        Math.abs(i - j));



	            // 排序后，选择移动代价最少的前 k + 1 个



	            Arrays.sort(move);



	            int sum = 0;



	            for (int k = 0; k < move.length; k++){



	                sum += move[k];



	                if (sum > m)



	                    break;



	                if (k + 1 > maxLen)



	                    maxLen = k + 1;



	            }



	        }



	    }



	    System.out.println(maxLen);



	}