如果不考虑环形字符串,我们可以怎么求得结果?

答:遍历字符串,当遇到不同字符时,统计当前字符出现的长度,对比当前已记录长度并更新,最后更新当前字符,代码如下:


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;
}