400395: GYM100162 B Circle of Stones

There are n stones on the table in a circle, each of them has a color. Colors are represented by lowercase English letters, so there are 26 possible colors. Different stones can have equal colors.

The circle of stones is called motley if every two neighboring stones have different colors. Stones in a circle are considered neighboring if there are no other stones between them in at least one direction. For example, the 1st and the 2nd stones are neighboring, as well as the 2nd and the 3rd, or the n-th and the 1st.

You are allowed to take away any (possibly empty) sequence of consecutive stones. And you can do this operation only once.

Determine for each k (0 ≤ k < n) if it is possible to take away k stones so that the resulting circle would be motley.

The input contains several test cases. Each test case is a single line, which is a description of n stones lying on the table (1 ≤ n ≤ 10⁶). This line contains only lowercase English letters.

For each test case, display the case number and a string of n digits. The k-th digit (0-indexed) must be "1" if it is possible to take away a segment of k consecutive stones so that the resulting circle would be motley. Otherwise the k-th digit must be "0".

rrg
rrrrr
brbg
abab

Case 1: 011
Case 2: 00001
Case 3: 1111
Case 4: 1011