编程题2

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


/**
 * 利用前缀和数组
 * 例如：
 * n=10,m=1,s=baabaabaab
 *   b a a b a a b a a b
 *   0 1 2 3 4 5 6 7 8 9
 *   
 *   将 b-->a
 *   b 的前缀和数组为
 *          sums={ 0, 3, 6, 9, 10}//10 为字符串长度
 *   计算长度分别为: 
 *          3  6-0-1=5   9-3-1=5  10-6-1=3
 *     ==>>max = max{ max, sums[i]-sum[i-m-1]-1}
 */

public class Main{
    public static int change(int n, int m, String s, char k) {
        int max = 0;
        List<Integer> sums = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == k) {
                sums.add(i);
            }
        }
        if (sums.size() <= m) {
            return n;
        }
        sums.add(s.length());
        max = sums.get(m);
        for (int i = m + 1; i < sums.size(); i++) {
            max = Integer.max(max, sums.get(i) - sums.get(i - m - 1) - 1);
        }
        return max;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        String s = scanner.next();
        System.out.println(Integer.max(change(n, m, s, 'a'), change(n, m, s, 'b')));
    }
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    int n, m;
    scanf("%d%d", &n, &m);
    cin>>s;
    int l=0, r=0, a=0, b=0, Max=0;
    for(;r<=n;r++){
        if(s[r]=='a')
            a++;
        else
            b++;
        if(a>m && b>m){
            Max = max(Max, r-l);
            if(s[l]=='a')
                a--;
            else
                b--;
            l++;
        }
    }
    Max = max(Max, r-l);
    printf("%d\n", Max);
    return 0;
}

# O(n)复杂度的解法
def main(s,m):

    a_index = [i for i in range(len(s)) if s[i] == 'a']
    b_index = [i for i in range(len(s)) if s[i] == 'b']
    a_index = [-1] + a_index + [len(s)]
    b_index = [-1] + b_index + [len(s)]
    if len(a_index)-2 <= m or len(b_index)-2 <= m:
        return len(s)
    else:
        max_a = [a_index[i+m]-a_index[i-1]-1 for i in range(1,len(a_index)-m)]
        max_b = [b_index[i+m]-b_index[i-1]-1 for i in range(1,len(b_index)-m)]
        return max(max_a+max_b)

n,m = list(map(int,input().strip().split()))
s = input().strip()

print(main(s,m))

#include <bits/stdc++.h>
using namespace std;
int presuma[50005];
int presumb[50005];
int main() {
    int n, m; cin >> n >> m;
    string s; cin >> s;
    for (int i=0; i<n; i++) {
        if (s[i] == 'a') {
            presuma[i+1] = presuma[i] + 1;
            presumb[i+1] = presumb[i];
        }
        else {
            presuma[i+1] = presuma[i];
            presumb[i+1] = presumb[i] + 1;
        }
    }
    int i=1, j=1, ans = 0;
    while(j <=n) {
        if (presuma[j] - presuma[i-1] <= m) {
            ans = max(ans, j-i+1);
            j++;
        } else {
            i++;
        }
    }
    i = 1; j = 1;
    while(j <=n) {
        if (presumb[j] - presumb[i-1] <= m) {
            ans = max(ans, j-i+1);
            j++;
        } else {
            i++;
        }
    }
    cout << ans << endl;
    return 0;
}

	

链接：https://blog.csdn.net/ansizhong9191/article/details/88365647

以b替换a为例，记录每一个b的位置，那么将连续m个b的置换为a必然存在最长的字串。对索引为i的b而言，将前面m个b置换为a，此时索引为i的b与索引为i-m-1的b之间的字串的长度为loc[i] - loc[i-m-1]-1。初始化时，i从m+1开始，因为前面不足m个b的时候，只要全部置为a即可。

``` python
def change(alpha):  
    loc = list() # loc存的是当前字符是ALPHA的位置  
    for i in range(len(s)):  
        if s[i] == alpha:  
            loc.append(i)
    loc.append(n) # 最后一个alpha以后的另一种字符情况也要计算，所以要加上len(s)              
    length = loc[m] # 当所有字符都为alpha是，最大的连续字符情况是m,所以说长度一定大于m\  
    for i in range(m + 1, len(loc)):          
        length = max(length, loc[i] - loc[i - m] - 1) 
    return length
n, m = list(map(int, input().split()))
s = input() print(max(change('a'), change('b')))

```

import java.util.Scanner;
public class Main {
    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            int n=scan.nextInt();
            int m=scan.nextInt();
            String s=scan.next();
            int a=get('a',n,m,s);
            int b=get('b',n,m,s);
            System.out.println(Math.max(a,b));
        }
    }
    public static int get(char ch,int n,int m,String s){
        int []data=new int[n+2];
        data[0]=-1;
        int poi=1;
        for(int i=0;i<n;i++){
            if(s.charAt(i)==ch){
                data[poi]=i;
                poi++;
            }
        }
        data[poi]=n;
        int ans=0;
        for(int i=0;i+m+1<=poi;i++){
            ans=Math.max(ans,data[i+m+1]-data[i]-1);
        }
        if(m>=poi)
            return n;
        else
            return ans;
    }
}

## 19:45 -- 20:27
n, m = [int(x) for x in input().split()]
s = input()
max_a = 0
max_b = 0
a_index = []
b_index = []
for i in range(n):
    if s[i] == 'a':
        a_index.append(i)
    else :
        b_index.append(i)
if len(a_index) <= m or len(b_index) <= m :
    print(n)
else :
    for i in range(len(a_index) - m):
        if i == 0:
            temp = a_index[m]
            if temp > max_b :
                max_b = temp
        elif i == len(a_index) - m :
            temp = n - a_index[i]
            if temp > max_b :
                max_b = temp
                print(i)
        else :
            temp = a_index[m+i] - a_index[i-1] - 1
            if temp > max_b :
                max_b = temp
    
    for i in range(len(b_index) - m):
        if i == 0:
            temp = b_index[m]
            if temp > max_a :
                max_a = temp
        elif i == len(b_index) - m :
            temp = n - b_index[i]
            if temp > max_a :
                max_a = temp
        else :
            temp = b_index[m+i] - b_index[i-1] - 1
            if temp > max_a :
                max_a = temp
    print(max(max_a, max_b))

#include<stdio.h>

char c[50010];
int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++) scanf("%c", &c[i]);
    int maxl=0, l=0, r=0, an=0, bn=0;
    while(r<=n){
        if(c[r]=='a') an++;
        else bn++;
        if(an<=m||bn<=m){
            r++;
        }else{
            if((r-l)>maxl) maxl=r-l;
            if(c[l]=='a'){
                l++;
                an--;
            }else{
                l++;
                bn--;
            }
            r++;
        }
    }
    if((r-l)>maxl) maxl=r-l;
    printf("%d", maxl);
    return 0;
}

def length(s, n, m):
    res = m                    # 初始化长度为m，因为即使是把前m个字符全改成a或b也没问题
    num_a = s[:m].count("a")   # 记录a的个数
    num_b = m - num_a          # 记录b的个数
    start = 0                  # 记录起始下标
    for i in range(m, n):      # 开始遍历
        if s[i]=='a':
            num_a += 1         # 更新a的个数
        else:
            num_b += 1         # 更新b的个数
        if min(num_a, num_b) <= m:    # 这种情况说明m个替代操作内可以使字符串变成一种
            res = max(res , i-start+1)# 以s[i]结尾的情况下的最大长度为i-start+1
        elif s[start] == 'a':  # 当a和b的长度都超过m时，起点必须要变才能使m个操作内的替代成立
            num_a -= 1         # 如果起点位置为a，则更新a的个数
            start += 1         # 更新起点位置
        else:
            num_b -= 1         # 如果起点位置为a，则更新a的个数
            start += 1         # 更新起点位置
    return res
n,m = map(int, input().split(' '))
s = input()
print(length(s, n, m))

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int m = in.nextInt();
        int k = in.nextInt();
        in.nextLine();
        String s = in.nextLine();
        int cnt = 0;
        int l=0, r = 0, ant = 0, bnt = 0;
        int res = 0;
        while(r < m){
            char c = s.charAt(r);
            if(c == 'a'){
                ant++;
            }else{
                bnt++;
            }

            while(Math.min(ant,bnt) > k){
                if(s.charAt(l)=='a'){
                    l++;
                    ant--;
                }else{
                    l++;
                    bnt--;
                }
            }
            res = Math.max(res, r - l+1);
            r++;
        }
        System.out.println(res);   
    }
}

n,m=map(int,input().split())
s=list(input())

def getmax(s,m,c):
    left,right,ans,cnt=0,0,0,0
    while right<len(s):
        if s[right]==c:right+=1
        else:
            cnt+=1
            right+=1
            # 这里因为用了一次修正所以 right往后移动一次
            while(cnt>m):
                # 超过修正次数了
                if s[left]!=c:cnt-=1
                left+=1
        ans=max(ans,right-left)
    return ans

max_len=0
max_len=max(getmax(s,m,'b'),getmax(s,m,'a'))
print(max_len)

官方题解的GO版本

package main

import(
    "fmt"
    "bufio"
    "os"
)

func main() {
    var n, m int
    fmt.Scan(&n)
    fmt.Scan(&m)
    reader := bufio.NewReaderSize(os.Stdin, n)
    line, _, _ := reader.ReadLine()
//     fmt.Println(max(arraySolve(n, m, line, 'a'), arraySolve(n, m, line, 'b')))
    fmt.Println(windowSolve(line, m, n))
}

func arraySolve(n, m int, s []byte, c byte) int {
    res := 0
    indexes := make([]int, 0) //存储所有的a/b字符的下标
    for i := 0; i < n; i++ {
        if s[i] == c {
            indexes = append(indexes, i)
        }
    }

    // 全部替换即可
    if len(indexes) <= m {
        return n
    }

    // 在最后面补一位,防止漏掉最后一个连续子串的情形
    indexes = append(indexes, n)
    // indexes[m]表示前面刚好有m个a/b,将它们全部替换掉得到的子串长度res即为indexes[m]指向的下标
    res = indexes[m]
    for i := m+1; i < len(indexes); i++ {
        // indexes[i] 与 indexes[i-m-1]之间共有m+1个a/b,而indexes[i-m-1]本身就是a/b,因此再减去1,就可以得到最长子串
        res = max(res, indexes[i]-indexes[i-m-1]-1)
    }
    return res
}

func windowSolve(str []byte, m, n int) int {
    var res int
    left, right := 0, 0
    cntA, cntB := 0, 0 
    for right < n {
        if str[right] == 'a' {
            cntA++
        } else {
            cntB++
        }
        if cntA > m && cntB > m {
            res = max(res, right-left)
            if str[left] == 'a' {
                cntA--
            } else {
                cntB--
            }
            left++
        }
        right++
    }
    res = max(res, right-left)
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}