一个项链由红蓝白三色珠子随机组成,珠子总数大于3小于350。找出一个分割点,从该点往前单色珠子数量加上往后的单色珠子数量为最大,白色珠子可以当作红蓝任意一个颜色处理。
给定一个字符串代表珠子的组成,其中字母 w 代表白色珠子,字母 b 代表蓝色珠子,字母 r 代表红色珠子。
输入样例:
“wwwbbrwrbrbrrbrbrwrwwrbwrwrrb”
输出样例:
11
上面的输入样例可以用下图来表示,从图中黄色短线处分割,前后有六个蓝色珠子和加五个红色珠子,总共11个珠子为最大值。
【算法思路】
- 方法一:暴力破解
- 我们可以采取暴力破解的方法,循环项链的每一个珠子,检查当前位置前后单色珠子的数量之和,这样就可以找出最大值。
- 注意输入样例是一个字符串,所以我们需要重复检查字符串开始和结束的位置以模拟完整项链的情形。
- 时间复杂度:O(n2)
- 方法二:DP 动态规划
- 将两个相同的输入字符串连接在一起,这样就可以将环形搜索改成线性搜索。然后检查每一个断点的前后单色珠子数量。
- 时间复杂度:O(n)
下面的动图展示了搜索的过程。