Educational Codeforces Round 110 Unstable String Solution (Java/C++)

Solution:

First, consider if the string is unstable, then how many substrings is beautiful. For 010101, we found it can have 6 substrings which length is 1, and 5 substrings which length is 2, …, and 1 substring which length is 6. And of course, all these substrings are unstable. So that, for any unstable string which length is n, there are $\frac{n\cdot(n+1)}{2}$ substring which is beautiful.

Now, let us consider the string like 0011 which is not unstable string in the beginning. We can find that, for this string, can be split to 3 unstable substrings: 0, 01 and 1. And these unstable substrings we can follow the above way to get the number of beautiful substrings.

So, now the question is changed to finding the longest contiguous unstable substrings. We found that: there only have two distinct modes of unstable substring: 0101... or 1010.... So, we can use the string to match the mode. If it can match, then it can be an unstable substring.
For example, 0??0. We use 0101 first. Then we found can match 010, and the last 0 cannot match. (The two question marks are replaced by 1 and 0.)
We use 1010. We found the first 0 cannot match, and last three can match as 010.  (The two question marks are replaced by 0 and 1.)

The last thing is the question marks will be count twice. For example, 0??0, the 0[10] from 0101 and the [01]0 from 1010 (the number inside [] represent the numbers replaced from "?"). So just need to subtract it.

So, for 0??0, there are $\frac{3\cdot(3+1)}{2}+\frac{3\cdot(3+1)}{2}-\frac{2\cdot(2+1)}{2}$ beautiful substrings.

Another example, the 3rd sample data: ?10??1100
Match 010101010. Get two unstable substrings: $\begin{matrix}
[?10??1]10[0]\\
[010101]01[0]\\
\end{matrix}$.
Match 101010101. Get 3 unstable substrings: $\begin{matrix}
[?]10[??]1[10]0\\
[1]01[01]0[10]1\\
\end{matrix}$.
And there are two contiguous question marks: [?]10[??]1100.
So, there are: $(\frac{6\cdot(6+1)}{2}+\frac{1\cdot(1+1)}{2})+(\frac{1\cdot(1+1)}{2} +\frac{2\cdot(2+1)}{2}+\frac{2\cdot(2+1)}{2})-\frac{1\cdot(1+1)}{2}-\frac{2\cdot(2+1)}{2}=25$ beautiful substrings.

Code:

Java

C++