Alternative Thinking
Contest: Codeforces Round 334 (Div. 1)
Difficulty rating: 1600
Tags: dp, greedy, math

Kevin has just recevied his disappointing results on the USA Identification of Cows Olympiad (USAICO) in the form of a binary string of length n. Each character of Kevin's string represents Kevin's score on one of the n questions of the olympiad—'1' for a correctly identified cow and '0' otherwise.

However, all is not lost. Kevin is a big proponent of alternative thinking and believes that his score, instead of being the sum of his points, should be the length of the longest alternating subsequence of his string. Here, we define an alternating subsequence of a string as a not-necessarily contiguous subsequence where no two consecutive elements are equal. For example, {0, 1, 0, 1}, {1, 0, 1}, and {1, 0, 1, 0} are alternating sequences, while {1, 0, 0} and {0, 1, 0, 1, 1} are not.

Kevin, being the sneaky little puffball that he is, is willing to hack into the USAICO databases to improve his score. In order to be subtle, he decides that he will flip exactly one substring—that is, take a contiguous non-empty substring of his score and change all '0's in that substring to '1's and vice versa. After such an operation, Kevin wants to know the length of the longest possible alternating subsequence that his string could have.

Input format:
The first line contains the number of questions on the olympiad n (1 ≤ n ≤ 100 000).

The following line contains a binary string of length n representing Kevin's results on the USAICO.

Output format:
Output a single integer, the length of the longest possible alternating subsequence that Kevin can create in his string after flipping a single substring.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, Kevin can flip the bolded substring '10000011' and turn his string into '10011011', which has an alternating subsequence of length 5: '10011011'.

In the second sample, Kevin can flip the entire string and still have the same score.

Example input:
8
10000011

Example output:
5

Example input:
2
01

Example output:
2

Editorial:
Hint: Is there any easy way to describe the longest alternating subsequence of a string? What happens at the endpoints of the substring that we flip?
Imagine compressing each contiguous block of the same character into a single character. For example, the first sample case '10000011' gets mapped to '101'. Then the longest alternating subsequence of our string is equal to the length of our compressed string. So what does flipping a substring do to our compressed string? To answer this, we can think about flipping a substring as flipping two (possibly empty) prefixes. As an example, consider the string '10000011'. Flipping the bolded substring '10000011' is equivalent to flipping the two bolded prefixes '10000011' and '10000011'.
For the most part, flipping the prefix of a string also flips the corresponding portion of the compressed string. The interesting case occurs at the endpoint of the prefix. Here, we have two possibilities: the two characters on either side of the endpoint are the same or different. If they are the same ('00' or '11'), then flipping this prefix adds an extra character into our compressed string. If they are different ('01' or '10'), we merge two characters in our compressed string. These increase and decrease, respectively, the length of the longest alternating subsequence by one. There is actually one more case that we left out: when the endpoint of our prefix is also an endpoint of the string. Then it is easy to check that the length of the longest alternating subsequence doesn't change.
With these observations, we see that we want to flip prefixes that end between '00' or '11' substrings. Each such substring allows us to increase our result by one, up to a maximum of two, since we only have two flips. If there exist no such substrings that we can flip, we can always flip the entire string and have our result stay the same. Thus our answer is the length of the initial longest alternating subsequence plus $$\min(2,\# \text{ of } '00' \text{ and } '11' \text{ substrings})$$.
A very easy way to even simplify the above is to notice that if the initial longest alternating subsequence has length  len - 2, then there will definitely be two '00' or '11' substrings. If it has length n - 1, then it has exactly one '00' or '11' substring. So our answer can be seen as the even easier $$\min(n,\text{longest alternating subsequence}+2)$$.