贪心求最长连续字符串

贪心算法 每次寻找当前最优解去更新

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String s = sc.next();
        int max = 0;
        System.out.println(Math.max(solve(n, m, s, 'a'), solve(n, m, s, 'b')));
    }
    public static int solve(int n, int m, String s, char c){
        int res = 0;
        List<Integer> index = new ArrayList<>();
        for(int i = 0; i < n; i++){
            if(s.charAt(i) == c){
                index.add(i);
            }
        }
        //如果要替换的字符个数 < 可替换个数，那么直接全部替换即可
        if(index.size() <= m){
            return n;
        }
        index.add(s.length());
        //len初始为按照顺序替换的第m个的下标
        res = index.get(m);
        for(int i = m + 1; i < index.size(); i++){
            //最大的肯定是m个，m区间 m-1的索引到m-1+m的索引
            //每次都选择最优解
            res = Math.max(res, index.get(i) - index.get(i - m - 1) - 1);
        }
        return res;
    }                 
}

滑动窗口

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String s = sc.next();
        int max = 0;
        System.out.println(windowSolve(n, m, s));
    }
    public static int windowSolve(int n, int m, String s){
        int res = Integer.MIN_VALUE;
        int left = 0, right = 0;
        int an = 0, bn = 0;
        while(right < n){
            if(s.charAt(right) == 'a'){
                an++;
            }else{
                bn++;
            }
            if(an <= m || bn <= m){
                right++;
            }else{    //此时窗口已经出现了m个可以改变的字符了
                res = Math.max(res, right - left);
                if(s.charAt(left) == 'a'){
                    left++;
                    an--;
                }else{
                    left++;
                    bn--;
                }
                right++;
            }
        }
        res = Math.max(res, right - left);
        return res;
    }


}