首页 > 试题广场 >

编程题2

[编程题]编程题2
  • 热度指数：387 时间限制：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' 子串。
算法知识视频讲解
添加回答
泣血残阳头像 泣血残阳
使用two pointer策略可以求解，首先从起点位置，取得最多进行n次变换得到的连续a串，然后每次删除头部的一次变换，再在尾部添加一次变换，注意添加尾部的变换后，需要将其后相邻的连续a串计数。
发表于 2018-02-21 11:28:40 回复(0)
牛客8046156号头像 牛客8046156号 
#解析：https://blog.csdn.net/weixin_42001089/article/details/87114410
n,m = [int(e) for e in input().split()]
Str = input()
result = 0
a_count = 0
b_count = 0
q = []
for e in Str:
    if e=='a':
        a_count+=1
    if e=='b':
        b_count+=1
    if a_count>m and b_count>m:
        if e=='a':
            while True:
                if q[0]=='a':
                    q.pop(0)
                    break
                q.pop(0)
                b_count-=1
            a_count-=1
        else :
            while True:
                if q[0]=='b':
                    q.pop(0)
                    break
                q.pop(0)
                a_count-=1
            b_count-=1
    q.append(e)
    result = max(result,len(q))
print(result)

发表于 2019-02-18 13:34:25 回复(1)
牛客1659416头像 牛客1659416
以第i个字符为起点向右走分别记录a和b出现的次数直到a和b出现的次数都大于m时停止，
这时走的长度即为以第i个字符为起点的字符串在至多m次变换下能够获得的最大连续子串的长度。
遍历全部n个字符，更新最大的长度即可。 

	#include <iostream>





	#include <string>





	#include <algorithm>





	 





	usingnamespacestd;





	 





	intmain()





	{





	    intn,m;





	    while(cin>>n>>m)





	    {





	        string str;





	        cin>>str;





	        if(n<=2*m+1)





	            cout << n << endl;





	        else





	        {





	            intl=0;





	            inta=0,b=0;





	            intright=0;





	            for(inti=0; i<n-2*m-1; i++)





	            {





	                if(i>0)





	                {





	                    if(str[i-1]=='a')





	                    {





	                        a--;





	                    }





	                    else





	                    {





	                        b--;





	                    }





	                }





	                for(intj=right; j<n; j++)





	                {





	                    if(str[j]=='a')





	                        a++;





	                    else





	                        b++;





	                    if(j-i+1>2*m+1)





	                    {





	                        if(a>m && b>m)





	                        {





	                            if(j-i>l)





	                                l=j-i;





	                            right=j+1;





	                            break;





	                        }





	                    }





	                }





	            }





	            cout << l << endl;





	        }





	    }





	    return0;





	}

发表于 2018-03-24 22:48:18 回复(0)
了不起的艾斯比头像 了不起的艾斯比


#include <iostream>

#include <string>

#include <algorithm>



using namespace std;
#define max(a, b)  (((a) > (b)) ? (a) : (b))
#define min(a, b)  (((a) > (b)) ? (b) : (a))


int main()

{

    int n, m;

    while (cin >> n >> m)

    {

        string str;

        cin >> str;

        if (n <= 2 * m + 1)

            cout << n << endl;

        else

        {

            int max = 0;
            for (int i = 0; i < n; i++)
            {    
                int a = 0, b = 0,min=0;
                for (int j = i; j < n; j++)
                {
                    if (str[j] == 'a')
                        a++;
                    else
                        b++;
                    min = min(a, b);
                    if (min == m)
                        max = max(j-i + 1,max);
                    
                }
                

            }

            cout << max << endl;        

        }

    }

    return 0;

}
发表于 2020-06-12 17:31:43 回复(0)
高星宇他大哥头像 高星宇他大哥 
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
 
int main()
{
    int n,m; //领扣424题
    while (cin>>n>>m) {
        string s;
        cin>>s;
        unordered_map<char,int> map1;
        int start=0,end=0,max_freq=0,res=0;
        while (end < n) {
            map1[s[end]]++;
            max_freq = max(max_freq,map1[s[end]]);
            if (end-start+1-max_freq > m) {
                map1[s[start]]--;
                start++;
            }
            res = max(res,end-start+1);
            end++;
        }
        cout<<res<<endl;
    }
}

发表于 2019-08-26 10:29:15 回复(0)
牛客141386712号头像 牛客141386712号 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;



int main()
{
    int n,m;
    cin>>n>>m;
    char c;
    string s;
    for(int i=0;i<n;++i)
    {
        cin>>c;
        s+=c;
    }
//    cout<<s<<endl;
    queue<int> que;
    int maxLen=0;
    int a_cnt=0,b_cnt=0;
    for(int i=0;i<s.size();++i)
    {
//        que.push(s[i]);
        if(s[i]=='a') ++a_cnt;
        if(s[i]=='b') ++b_cnt;
        if(a_cnt>m && b_cnt>m)
        {
//            maxLen=que.size()>maxLen?que.size():maxLen;
            if(s[i]=='a')
            {
                while(que.front()!='a')
                {
                    que.pop();
                    --b_cnt;
                }
                que.pop();
                --a_cnt;
            }
            else
            {
                while(que.front()!='b')
                {
                    que.pop();
                    --a_cnt;
                }
                que.pop();
                --b_cnt;
            }
        }
        que.push(s[i]);
        maxLen=que.size()>maxLen?que.size():maxLen;
    }

    cout<<maxLen<<endl;
    return 0;
}

/*
 10 2
 aabaabbbba
 */
编译是通过的，但是如果是10，2 aabaabbbba。运行结果是6，不知道为什么编译会通过？？
发表于 2019-08-17 16:44:11 回复(0)
提交观点

问题信息

贪心 字符串 算法工程师 2018 字节跳动
上传者：小小
难度：
6条回答 2035浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号