这道题要求我们求一个字符串，符合某个条件的最长子串的条件。按照题目要求，我们的目的就是找到合适的分割点，使得两边的字符串的和最长。

例如：rbrrrbbbrb，我们看到从中间分割的话，我们得到rrrbbb的子串，显然他是最长的。

从题意看，从任意一种相同颜色间隔来分割一定不会是最合算的。比如brrrb，我们这样分割，brr rb，我们得到的子串是rrr，而从rrr两边的任意一边分割，我们得到的长度都是rrr + x > rrr。显然，分割点一定是在颜色交错的地方最合算。

 

但是题目让人讨厌的地方有两点：

1.项链中有w元素，他既可以作为r也可以作为b。

2.项链是一个环，最长子串可能发生在数组尾部和头部的对接。

正如例题所示

wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb                       ****** *****                       rrrrrb bbbbb  <-- assignments                       5 x r  6 x b  <-- 11 total

 

如果你仔细思考扫描过程，你会发现很多地方是有重复扫描的。我们来看下一些比较典型的字符串

例如：rwrwrbbbbrrrr

1。显然我们不需要从每个rw交汇处去做分割然后扫描。所以这段rwrwr显然全部看成r。

2。在wrb除分割扫描后，bbb的长度已经知道，所以在后面一个br处，再回头扫描b显然没有什么必要。

所以我得出

1.“对于夹在同一颜色中间的所有w，就把它们看做是这种颜色的字串。”

2.在检查过一个分割点后，在下一个分割点，我们缓存左边的颜色，继而扫描右边的字串长度。

这样的话，我们的指针就可以一直往前走不走回头路了（循环回来情况不算）

 

但是到这里问题还没有全部解决，还有一种情况

rrr www bbb rrrrr b

碰到这种在r和b当中的www我们该如何处理？对于一次分割点检查来说，他的长度和 len(r) + len(w) + len(b) ，不需要归于左右。

但是我们需要缓存左边的值，等待与右边的值做比较。

比如检查好 rrr www bbb 后，我们要检查rrrrr，由于不走回头路，所以我们要知道rrrrr左边的b的长度。但是根据规则来看，左边的b长度不是3，

而是3+ len(w)=6。所以，我们在缓存长度的时候，需要将w的长度一起算上。

这样检查完rrrrr之后，看起来我们像是从 br中间各自检查了 www bbb 和 rrrrr，但其实我们只是缓存了www bbb。依次类推。

这样一来，一遍走下来，不回头也能算出结果，所以复杂度是O(n)。

当然，由于题目的特殊性，我们不能只在检查完最右边以后停下，而是应该回头检查完包含结尾字符串的那段子串以后才能停下。我的处理有些技巧的地方，使得他可以初值问题（不预先判断起点颜色），同时应对单色问题（即同一种颜色，算法也会终止），项链的循环问题（这个说起来太复杂了，还是看代码吧）。

 

#include 
     
      #include 
      
       #include 
       
        #include