JoJo's Incredible Adventures
Contest: Codeforces Round 866 (Div. 2)
Difficulty rating: 1100
Tags: math, strings, two pointers

Did you think there was going to be a JoJo legend here? But no, that was me, Dio!

Given a binary string $$$s$$$ of length $$$n$$$, consisting of characters 0 and 1. Let's build a square table of size $$$n \times n$$$, consisting of 0 and 1 characters as follows.

In the first row of the table write the original string $$$s$$$. In the second row of the table write cyclic shift of the string $$$s$$$ by one to the right. In the third row of the table, write the cyclic shift of line $$$s$$$ by two to the right. And so on. Thus, the row with number $$$k$$$ will contain a cyclic shift of string $$$s$$$ by $$$k$$$ to the right. The rows are numbered from $$$0$$$ to $$$n - 1$$$ top-to-bottom.

In the resulting table we need to find the rectangle consisting only of ones that has the largest area.

We call a rectangle the set of all cells $$$(i, j)$$$ in the table, such that $$$x_1 \le i \le x_2$$$ and $$$y_1 \le j \le y_2$$$ for some integers $$$0 \le x_1 \le x_2 < n$$$ and $$$0 \le y_1 \le y_2 < n$$$.

Recall that the cyclic shift of string $$$s$$$ by $$$k$$$ to the right is the string $$$s_{n-k+1} \ldots s_n s_1 s_2 \ldots s_{n-k}$$$. For example, the cyclic shift of the string "01011" by $$$0$$$ to the right is the string itself "01011", its cyclic shift by $$$3$$$ to the right is the string "01101".

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. The description of test cases follows.

The first and the only line of each test case contains a single binary string $$$s$$$ ($$$1 \le \lvert s \rvert \le 2 \cdot 10^5$$$), consisting of characters 0 and 1.

It is guaranteed that the sum of string lengths $$$|s|$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the maximum area of a rectangle consisting only of ones. If there is no such rectangle, output $$$0$$$.

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

Note:
In the first test case, there is a table $$$1 \times 1$$$ consisting of a single character 0, so there are no rectangles consisting of ones, and the answer is $$$0$$$.

In the second test case, there is a table $$$1 \times 1$$$, consisting of a single character 1, so the answer is $$$1$$$.

In the third test case, there is a table:

101110011

In the fourth test case, there is a table:

011110001111100111110011111001111100

In the fifth test case, there is a table:

101010010101101010010101101010010101

Rectangles with maximum area are shown in bold.

Example input:
5
0
1
101
011110
101010

Example output:
0
1
2
6
1

Editorial:
First of all, consider the cases if the given string consists only of ones and only of zeros. It's easy to see that answers for these cases are $$$n^2$$$ and $$$0$$$.
In all other cases let's split all strings into segments that consist only of ones. Also if the first and the last characters of the string equals to "1", these two characters will be in one segment. In other words, the pair of ones will lay inside one group if there exists some cyclic shift that these two ones are consecutive. Let the maximum length of such segment be equal to $$$k$$$. Then it can be shown that the answer equals to $$$\lfloor \frac{k+1}{2} \rfloor \cdot \lceil \frac{k+1}{2} \rceil$$$.
We will proof this fact in such way. If there exists some rectangle of size $$$a \times b$$$. Considering its first row, we can see that it has $$$a+b-1$$$ consecutive ones. But it means that $$$a+b \leq k+1$$$. Without loss of generality, if $$$a \le b$$$, we can do the following replacements: $$$a = \lfloor \frac{k+1}{2} \rfloor - \lambda$$$, $$$b = \lceil \frac{k+1}{2} \rceil + \lambda$$$. It means that $$$ab = \lceil \frac{k+1}{2} \rceil \cdot \lfloor \frac{k+1}{2} \rfloor - \lambda^2 \le \lceil \frac{k+1}{2} \rceil \cdot \lfloor \frac{k+1}{2} \rfloor$$$.
Time complexity: $$$\mathcal{O}(n)$$$.