1.考虑将例子中的10010 复制一份得到1001010010。
2.将10010分为10与010翻转并拼接变为01010。
这个操作实际上就是1001010010中的第3到第7位。
进而我们发现可以将字符串看成一个环(首尾相连),那么任意一次操作都可以在环上找到对应的子串,于是就可以化环为链,在环上找最长的连续交替01串。
给定长度为n的01串,定义一次操作为,将整个字符串按顺序分为两部分,将两部分各自翻转后再按原顺序拼接。
提问,进行任意次的操作后,可以得到的最长的连续的01交替的子串有多长。
例:原01串为01001,可以先将原串分为010和01两部分,分别翻转得到010和10,按原顺序拼接后得到01010,此时最长的连续交替子串为01010,长度为5
第一行输入n表示输入的01串的长度。(1≤n≤2∗106)
第二行输入长度为n的01串
输出一个数字表示可能得到的最长的交替01子串的长度。
输入
5
10010
输出
5
说明
原字符串分为10和010,分别翻转得到01和010,拼接后为01010