CF603A Alternative Thinking

Kevin 刚刚收到了 USA Identification of Cows Olympiad（USAICO，奶牛识别奥林匹克竞赛）成绩单，成绩以一个长度为 $n$ 的二进制字符串给出。Kevin 的字符串中，每个字符表示他在 $n$ 道题中的一题得分——答对奶牛则为 '1'，否则为 '0'。 不过，一切还未失去希望。Kevin 非常推崇另类思考，他认为自己的分数，应当是字符串中最长交错子序列的长度。这里，我们定义交错子序列为不一定连续的子序列，且没有两个相邻元素相同。例如，$ {0,1,0,1} $、$ {1,0,1} $ 和 $ {1,0,1,0} $ 是交错序列，而 $ {1,0,0} $ 和 $ {0,1,0,1,1} $ 则不是。 Kevin 是个小机灵鬼，甚至愿意黑进 USAICO 的数据库来提高自己的分数。为了不引人注意，他决定只翻转恰好一个子串——即选取字符串中的一个连续非空子串，将其中的所有 '0' 变为 '1'，所有 '1' 变为 '0'。在做此操作后，Kevin 想知道，他的字符串可能获得的最长交错子序列的长度是多少。

第一行包含一个整数 $n$，表示竞赛题目数量（$1 \leq n \leq 100000$）。 第二行一个长度为 $n$ 的二进制字符串，表示 Kevin 在 USAICO 上的成绩。

输出一个整数，表示 Kevin 经过一次翻转操作后，他的字符串可能得到的最长交错子序列的最大长度。

在第一个样例中，Kevin 可以翻转标记为粗体的子串 '10000011'，将原串变为 '10011011'，此时有长度为 5 的交错子序列：'10011011'。 在第二个样例中，Kevin 可以直接翻转整个字符串，最终交错子序列的长度不会变化。 由 ChatGPT 5 翻译