首页 > 试题广场 >

编程题2

[编程题]编程题2
  • 热度指数:197 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
有一个仅包含’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' 子串。
def solve(n, m, s):
    length = m     # 长度至少可以达到操作数的上限
    cnt_a = s[:m].count('a')
    cnt_b = m - cnt_a
    start = 0      # 最大连续的相同字符的子串的起始索引
    for i in range(m, n):
        if s[i] == 'a':
            cnt_a += 1         # 更新a的个数
        else:
            cnt_b += 1         # 更新b的个数
        if min(cnt_a, cnt_b) <= m:
            # 说明从对子串s[:i+1]进行不超过m个操作就可以使字符串变成一种
            # 如果a的数目少,就在m个操作内将a全部变为b,如果b的数目少则将b全部变为a
            length = max(length , i - start + 1)      # 更新长度
        elif s[start] == 'a':  
            # 当a和b的长度都超过m时,起点必须要向右移动才能使m个操作内的替代成立
            cnt_a -= 1         # 如果起点位置为a,则更新a的个数
            start += 1         # 更新起点位置
        else:
            cnt_b -= 1         # 如果起点位置为b,则更新b的个数
            start += 1         # 更新起点位置
    return length

if __name__ == "__main__":
    n, m = map(int, input().strip().split())
    s = input().strip()
    print(solve(n, m, s))

发表于 2021-01-26 15:49:29 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

string str;
int n, m;

int change_alpha(char k)
{
    vector<int> loc;
    for (int i = 0; i < n; ++i)
        if (str[i] == k) loc.push_back(i);
    loc.push_back(n);
    int max_length = loc[m];          //从头变a/b的初始长度

    for (int i = m + 1; i < loc.size(); ++i) {
        // loc[i]当前k实际索引, loc[i-m-1] i的前面m个数翻转之后,再前面的未翻转k的索引
        // loc[i] - loc[i-m-1] - 1 之间翻转m个k之后,中间字符的长度。
        max_length = max(max_length, loc[i] - loc[i - m - 1] - 1);
    }
    return max_length;
}

int main()
{
    cin >> n >> m;
    cin >> str;

    cout << max(change_alpha('a'), change_alpha('b')) << endl;
}


发表于 2020-08-05 15:17:02 回复(0)
由于就两种字符,所以,我们可以先统计出它们出现的次数,比如aaaabbabbbaa,可以统计成4,2,1,3,2,那么假设我们的最长序列分别时从4,2,1,3,2的位置开始的,计算可能出现的最长的串,比如说m=4,那么从第一个字符a开始,长度可以是4+2<耗掉2个>+1+2<耗掉2个> = 9,如果是从第一个b开始,则2+1<耗掉>+3+2<耗掉> = 8,注意,此处还有一个可以用,所以向前扩展,再加1,也是9,依次类推吧。。。
发表于 2019-11-21 15:08:35 回复(0)