题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

复制

8 1
aabaabaa

输出

复制

5

说明

把第一个 'b' 或者第二个 'b' 置成 'a'，可得到长度为 5 的全 'a' 子串。

 

算法分析

该题有两种情况，一种是把字符b置换成a，另外一种是把字符a置换成b，不管是哪种情况，第一步就是把那种字符的索引的位置记录在一个数组里，然后逐个判断大小，max_length的初始值为vis[n],然后用O(n)算法让max_length与vis[i]-vis[i-n-1]-1依次比较，最后得出最大值，两个字符的最大值再比较得出最终的结果

 AC代码

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
import java.util.Vector;

public class test {
    public static String str;
    public static int m;
    public static int n;
    public static int change_alpha(char k)
    {
         int[] vis=new int[50000];
         int j=0;
         char[] str1=str.toCharArray();
         for(int i=0;i<m;i++)
         {
              if(str1[i]==k)
                  vis[j++]=i;
         }
         int max_length=vis[n];
         for(int i=n+1;i<j;i++)
             max_length=Math.max(max_length,vis[i]-vis[i-n-1]-1);
         return max_length;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        m=scan.nextInt();
        n=scan.nextInt();
        String s=scan.nextLine();
        str=scan.nextLine();
        System.out.println(Math.max(change_alpha('a'),change_alpha('b')));
    }
}