如果不考虑环形字符串,我们可以怎么求得结果?
答:遍历字符串,当遇到不同字符时,统计当前字符出现的长度,对比当前已记录长度并更新,最后更新当前字符,代码如下:
int func1(string s){
int res = 0;//作为输出结果,记录最大长度
char cur = s[0];//cur 为当前字符,初始化为s [0],然后从下标1开始遍历
int n = s.size();
int tmp = 1;//记录当前字符cur 连续出现的次数,初始时s[0]出现1次,所以初始化为 1
for(int i = 1; i < n; i++){
if(s[i] != cur){//出现不同字符
res = max(res, tmp);//更新结果
cur = s[i];//更新字符
tmp = 1;//当前字符s[i]出现了1次
}
else{
//字符相同,当前字符长度+1
tmp++;
}
}
/*
针对情况"aaa",统计到最后结果是res = 0, tmp = 3,即最后出现的连续字符串不会被统计到
因此这里返回max(res, tmp)
*/
return max(res, tmp);
}
进入正题:
方法(1):
①遇到首尾相连/环形,通常可以尝试构造一个新字符串new_s为2个原字符串的拼接;
②接下来我们举个例子分析,假设字符串 s = "aapppaa",预期结果 = 4, 则new_s = "aapppaaaapppaa",可以看出这段就出现了长度为4的合法结果字符串。
③思考一下有没有特例:s = "aaaa",构造后new_s = "aaaaaaaa",结果变成8了,我们只需要限制结果不超过原字符串即可
int main(){
string s;
cin >> s;
int n = s.size();
string new_s = s + s;
int ans = min(func1(new_s), n);
cout<<ans;
}
法(2):如果想不到上面拼接字符串的思路,正常做也可以:
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int n = s.size();
int ans = 0, tmp = 1;
char cur = s[0];
for(int i = 1; i < n; i++){
if(s[i] == cur){
tmp++;
}
else{
ans = max(ans, tmp);
tmp = 1;
cur = s[i];
}
}//写法类似上面提到的func1
//此时cur存储的是最后一段连续字符串的长度,cur为最后一段连续字符串的字符
//直接遍历,遇到和cur不同的直接break
for(int i = 0; i < n; i++){
if(s[i] != cur){
break;
}
tmp++;
}
if(tmp > n){
cout<<n;//字符串的所有字符相同的情况下才会出现tmp > n
return 0;
}
ans = max(ans, tmp);
cout<<ans;
}



京公网安备 11010502036488号