描述

有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。

输入描述：

第一行两个整数 n , m (1<=m<=n<=50000)，第二行为长度为n且只包含’a’和’b’的字符串s。

输出描述：

输出在操作次数不超过 m 的情况下，能够得到的 最大连续 全’a’子串或全’b’子串的长度。

题解：

最长可翻转字符串长度，由于题目只有’a’,b’两种字符字母，我们只需要统计字母’a’的下标，利用前缀和思想，统计满足最大翻转次数的区间长度并判断取最大值。

import java.util.*;
public  class Main {
          
   
    public static void main(String []args) {
          
   
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        String str = scanner.next();
        System.out.println(Math.max(helper(n,m,str,a),helper(n,m,str,b)));
    }
    public static int helper(int n, int m, String str,char a) {
          
   
        int max = 0;
        List<Integer> preSum = new ArrayList<>();
        //统计字母的下标
        for(int i = 0; i < str.length(); i++) {
          
   
            if(str.charAt(i) == a){
          
   
                preSum.add(i);
            }
        }
        //若变化的字母个数小于最大翻转次数，直接返回字符串长度
        if(preSum.size() < m) return n;
        //需要将字符串长度push到列表中
        preSum.add(str.length());
        max = preSum.get(m);
        //统计满足最大翻转次数的区间长度并判断取最大值
        for(int i = m+1; i < preSum.size(); i++) {
          
   
            max = Math.max(preSum.get(i) - preSum.get(i-m-1) - 1,max);
        }
        return max;
    }
}