#4003. 「USACO1.2」断开的项链 暂未评定

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

你有一条由 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 三种字符。

输出格式

共一行,包含一个整数表示我们可以收集珠子的最大数目。

样例

输入样例:

29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

输出样例:

11

数据范围与提示