题解

难度：中等

知识点：字符串的最长子串问题

分析

方法1：利用下标位置的普通方法,分a、b两种情况处理（较简单）

利用字符下标计算间隔长度，遍历字符串s，以b换a举例：返回所有b的索引值保存在数组中，存为数组indexes=[idx1,idx2,…]，（a换b一样）。计算m个b的最大间隔区间，如果b的个数小于等于m，即字符串中不足m个b，全部将他们替换成a即可；否则取“indexes[i]- indexes[i-m-1]-1”的长度的最大值max即为最大连续的相同字符的子串长度，但要注意首位元素的处理。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int oper = sc.nextInt();
        String str = sc.next();
        System.out.println(Math.max(arraySolve(len, oper, str, 'a'), arraySolve(len, oper, str, 'b')));

    }

    public static int arraySolve(int n, int m, String s, char c) {
        int res = 0;
        List<Integer> indexes = new ArrayList<>();  // 用来存储a/b的所有下标位置
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) {  //用c来替换其他字符，将c所在下标位置加入
                indexes.add(i);
            }
        }

        // 如果要替换的字符个数小于可替换个数，那么直接全部替换即可
        if (indexes.size() <= m) {
            return n;
        }

        // 注意端点位置的处理 
        indexes.add(s.length());
        res = indexes.get(m);
        for (int i = m + 1; i < indexes.size(); i++) {

            res = Math.max(res, indexes.get(i) - indexes.get(i - m - 1) - 1);
        }
        return res;
    } 

方法2：滑动窗口思想解决（要想到连续子串问题都可以用滑动窗口思想来解决）

① 对字符串设置left和right两个指针，初始化left=right=0；而闭区间[left,right]就是窗口。
② 不断增加窗口的right指针，直到窗口中满足题目要求，本题是闭区间中已经更改某个字符（a或b）m次了（用an或bn来表示次数情况），此时相当于找到了解题的可行解。
③ 由于本题是寻找最长子串，所以left指针和right指针要一起往右增加，并且当窗口中改变了相应m次值时更新结果，在一系列可行解中找最优解。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int oper = sc.nextInt();
        String str = sc.next();
        System.out.println(windowSolve(str, oper, len));

    }
    private static int windowSolve(String str, int oper, int len) {
        int res=Integer.MIN_VALUE;  
        int left=0, right=0;  // 滑动窗口设置两个指针lr
        int an=0, bn=0;   //用来计数窗口中a/b的个数

        while(right<len){
            if(str.charAt(right)=='a') {
                an++;
            }else {
                bn++;
            }
            // right一直往右走，寻找可行解
            if(an<=oper||bn<=oper){  
                right++;

            }else{  // 从可行解中找最优解：left开始往右走
                // 此时窗口中已经出现了oper个可以改变的字符,更新结果
                res = Math.max(res, right-left);

                // left指针往左走，窗口中退出一个字符相应的计数减1，
                // 而right指针新指的字符计数已经在刚进入while语句时的if判断已加1
                if(str.charAt(left)=='a'){  
                    left++;
                    an--;
                }else{
                    left++;
                    bn--;
                }
                right++;
            }
        }

        res = Math.max(res, right-left);
        return res;
    }
}