Alternative Thinking | Editorial by mynk322

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 100 00 011 is equivalent to flipping the two bolded prefixes 10000011 and 10000.

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 .

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 .

Code: http://codeforces.com/contest/603/submission/14608473

Alternative Thinking | Editorial by mynk322

Download submission

All caught up!

View submission

Is your resume even shortlisted?