CF1750B.Maximum Substring

A binary string is a string consisting only of the characters 0 and 1. You are given a binary string $s$.

For some non-empty substring$^\dagger$ $t$ of string $s$ containing $x$ characters 0 and $y$ characters 1, define its cost as:

• $x \cdot y$, if $x \gt 0$ and $y \gt 0$;
• $x^2$, if $x \gt 0$ and $y = 0$;
• $y^2$, if $x = 0$ and $y \gt 0$.

Given a binary string $s$ of length $n$, find the maximum cost across all its non-empty substrings.

$^\dagger$ A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

二进制字符串是指仅由字符 0 和 1 组成的字符串。现给定一个二进制字符串 $s$。

对于字符串 $s$ 的某个非空子串$^\dagger$ $t$，设其包含 $x$ 个字符 0 和 $y$ 个字符 1，则定义其代价为：

• 若 $x > 0$ 且 $y > 0$，代价为 $x \cdot y$；
• 若 $x > 0$ 且 $y = 0$，代价为 $x^2$；
• 若 $x = 0$ 且 $y > 0$，代价为 $y^2$。

给定长度为 $n$ 的二进制字符串 $s$，求其所有非空子串中的最大代价。

$^\dagger$ 字符串 $a$ 是字符串 $b$ 的子串，当且仅当 $a$ 可通过从 $b$ 的开头删除若干（可能为零或全部）字符、并从结尾删除若干（可能为零或全部）字符而得到。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

The second line of each test case contains a binary string $s$ of length $n$.

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print a single integer — the maximum cost across all substrings.

对于每个测试用例，输出一个整数——所有子串中的最大代价。

In the first test case, we can take a substring $111$. It contains $3$ characters 1 and $0$ characters 0. So $a = 3$, $b = 0$ and its cost is $3^2 = 9$.

In the second test case, we can take the whole string. It contains $4$ characters 1 and $3$ characters 0. So $a = 4$, $b = 3$ and its cost is $4 \cdot 3 = 12$.

In the third test case, we can can take a substring $1111$ and its cost is $4^2 = 16$.

In the fourth test case, we can take the whole string and cost is $4 \cdot 3 = 12$.

In the fifth test case, we can take a substring $000$ and its cost is $3 \cdot 3 = 9$.

In the sixth test case, we can only take the substring $0$ and its cost is $1 \cdot 1 = 1$.

在第一个测试用例中，我们可以选取子串 $111$。它包含 $3$ 个字符 1 和 $0$ 个字符 0。因此 $a = 3$，$b = 0$，其代价为 $3^2 = 9$。

在第二个测试用例中，我们可以选取整个字符串。它包含 $4$ 个字符 1 和 $3$ 个字符 0。因此 $a = 4$，$b = 3$，其代价为 $4 \cdot 3 = 12$。

在第三个测试用例中，我们可以选取子串 $1111$，其代价为 $4^2 = 16$。

在第四个测试用例中，我们可以选取整个字符串，其代价为 $4 \cdot 3 = 12$。

在第五个测试用例中，我们可以选取子串 $000$，其代价为 $3 \cdot 3 = 9$。

在第六个测试用例中，我们只能选取子串 $0$，其代价为 $1 \cdot 1 = 1$。