题目描述

你有一条由 N 个珠子串成的项链，珠子的颜色有红、白、蓝三种，珠子在项链中呈随机分布。

例如 N=29 时，两个项链的示例如下所示：

            1 2                               1 2
        r b b r                           b r r b
      r         b                       b         b
     r           r                     b           r
    r             r                   w             r
   b               r                 w               w
  b                 b               r                 r
  b                 b               b                 b
  b                 b               r                 b
   r               r                 b               r
    b             r                   r             r
     b           r                     r           r
       r       r                         r       b
         r b r                             r r w
        样例 A                            样例 B
                    r 红珠子
                    b 蓝珠子
                    w 白珠子

图片对项链的第一颗珠子和第二颗珠子进行了标记。

样例 A 中的项链只包含蓝红两种颜色的珠子，将所有珠子按顺序记录颜色为：

brbrrrbbbrrrrrbrrbbrbbbbrrrrb
假设你现在要将项链从某个点处断开，并将断开后的项链拉直摆放，然后从一端开始收集相同颜色的珠子，直到碰到另一种颜色的珠子为止，完成后在另一端进行相同的操作（这次收集的珠子的颜色可能与之前收集的颜色并不相同）。

现在，你需要判断在项链的哪一处将项链断开，可以使得我们收集珠子的数量达到最多。

例如，对于样例 A 提供的项链，我们在 9 号珠子和 10号珠子之间断开项链，或者在 24 号珠子和 25 号珠子之间断开项链，可以收集到最多 8 个珠子。

另外，某些项链除蓝红珠子外，还包含白珠子，如样例 B 所示。

收集珠子时，如果我们遇到了白色珠子，那么我们可以将它视为红色或蓝色，并将其涂上相应的颜色。

表示项链的字符串只包含 r,w,b 三种字符。

请你编写一个程序，求出我们可以收集珠子的最大数目。

输入格式
第一行包含整数 N，表示珠子的数量。

第二行包含一个由 N 个字符构成的字符串，字符串中只包含r,w,b 三种字符。

输出格式
共一行，包含一个整数表示我们可以收集珠子的最大数目。

数据范围
3≤N≤350

样例

输入样例：
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
输出样例：
11

算法1

(暴力枚举) $O(n^2)$

我们可以直接将字符串扩大一倍，然后分别从左右开始搜索，这里有两个需要注意的点：
1.第一个遇到的颜色可能是白色，那么我们可以将它变为最近遇到的颜色
2.如果收集到的珠子的数目大于项链中的珠子的数目，那么我们直接输出珠子的数目就可以了。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string str;
    cin>>str;
    str=str+str;//字符串扩大两倍
    int res=0;
    for(int i=0;i<n;i++)
    {
        int l=0;
        int j=i,k=0;//j是起点，k是偏移量
        char ch=str[j]; //第一个颜色，可能是白色
        while(k<n&&(str[j]==str[j+k]||str[j+k]=='w'||ch=='w'))//可能的匹配
        {
            if(ch=='w'&&str[j+k]!='w')//如果是白色更新为最近的颜色
                ch=str[j+k];
            l++;
            k++;
        }
        j=i+n-1,k=0;//另一个端点
        int r=0;
        ch=str[j-k];
        while(k<n&&(str[j]==str[j-k]||str[j-k]=='w'||ch=='w'))//可能的匹配
        {
            if(ch=='w'&&str[j-k]!='w') //如果是白色则更新为最近的颜色
                ch=str[j-k];
            r++;
            k++;
        }
        res=max(res,l+r);
    }
    if(res>n) res=n;//如果收到的珠子数目大于所有的珠子
    cout<<res<<endl;
    return 0;
}