标签搜索

目 录CONTENT

文章目录

字节--字符串翻转.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 5 阅读 / 1,617 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

字节--字符串翻转

@[toc]

一、题目描述

有一个仅包含’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

输出例子1:
5

例子说明1:
把第一个 'b' 或者第二个 'b' 置成 'a',可得到长度为 5 的全 'a' 子串。

二、分析

  •  该字符串非 a 即 b 也就是说在区间 l~r之间把所有字符变为 a 所需的步骤数是 该区间内 字符b 的数量。反之亦然.
  •  用数组 count[i] 表示 字符串中位置区间 0~i 包含的 a 的个数,则 区间 l~r 的 a 的个数为 count[r] - count[l - 1]
  •  b 的个数用 a 的个数算出 即 区间 l~r 的 b 的个数为 r + 1 - count[r] - (l + 1 - 1 - count[l - 1]) = r + 1 - l - count[r] + count[l - 1]
  •  在区间 l~r 的 a 和 b 的个数已知的情况下
  •  若 区间长度step内的 a 的个数 <= m 则 可以通过 m 个步骤 产生 长度为step的连续字符串 b
  •  若 区间长度step内的 b 的个数 <= m 则 可以通过 m 个步骤 产生 长度为step的连续字符串 a
  •  归纳为 :若 区间长度step内的字符 b 或字符 a 的个数 <= m 则 可以通过 m 个步骤 产生 长度为step的字符串(不管是全a还是全b)
  •  这样 就可以直接计算出一个字符串长度(区间长度step)是否可行,因此不需要进行递推,可以直接进行二分搜索,得到最大长度
  •  检查一个长度step是否可行的时间复杂度为O(n),二分搜索的时间复杂度为O(log n)。
  •  因此,该方法总的时间复杂度为 O(n*log n)

三、代码

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

//数组区间
int count[50005];
int n,m;
 
//检查当前区间长度(step)是否能在 m 个步骤内实现全 a 或 全 b 
bool func(int step)
{
    for(int i = 0;i + step < n;i++)
    {
        if(m >= step + 1 - (count[i + step] - count[i - 1]))
            return true;	//检查 a--》  公式 m>=区间内 b 的个数 
		if(m >= count[i + step] - count[i - 1])
            return true;	//检查 b--》  公式: m>=区间内 a 的个数 
    }
    return false;
}
 
 
int main()
{
    cin>>n>>m;
    string str;
    cin>>str;
    
    //输入并计算出 count 数组 
    int sum = 0;
    //统计0~i区间内的a的数量分别保存在每个count[i]位置
    for(int i = 0;i < str.size();i++)
    {
        if(str[i] == 'a')
            count[i] = ++sum;
        else 
            count[i] = sum;
    }
 
    //二分搜索最大区间值 
	int l = 0,r = n-1,mid; 
    while(l < r)
    {
    	//取中点,确定区间的大小
        mid = l + (r - l) / 2;
        //如果当前区间长度满足情况,需要睁增大区间长度
        if(func(mid))
        {
            l = mid + 1;
        }
        //反之缩小区间长度
        else
        {
            r = mid;
        }
    }

    cout<<l<<endl;
    return 0;    
}
0

评论区