Maximum Substring (Codeforces 1750B)
Tags: Greedy, brute force

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 > 0$$$ and $$$y > 0$$$;  $$$x^2$$$, if $$$x > 0$$$ and $$$y = 0$$$;  $$$y^2$$$, if $$$x = 0$$$ and $$$y > 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.

Input: 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$$$.

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

Note: 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$$$.

Sample Inputs:
6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0

Sample Outputs:
9
12
16
12
9
1

Solution (Python):
import sys
input = sys.stdin.readline
out = []
t = int(input())
for _ in range(t):
    input()
    s = input().strip()
    poss = []
    z = o = tz = to = 0
    for c in s:
        if c == '0':
            tz += 1
            z += 1
            o = 0
            poss.append(z * z)
        else:
            to += 1
            o += 1
            z = 0
            poss.append(o * o)
    poss.append(tz * to)
    out.append(max(poss))
print('\n'.join(map(str, out)))

Solution (Python):
def i():
    n = int(input())
    s = input() + 'z'
    c = 1
    p = 1
    o = s[-1] == '1'
    for (x, y) in zip(s, s[1:]):
        if x == y:
            p += 1
        else:
            if p > c:
                c = p
            p = 1
        if x == '1':
            o += 1
    return str(max(c * c, o * (n - o)))
t = int(input())
a = []
for _ in range(t):
    a.append(i())
print('\n'.join(a))

Solution (Python):
from sys import stdin, stdout

def inp():
    return int(stdin.readline())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s)])

def invr():
    return map(int, input().split())
''

def main():
    for i in range(inp()):
        n = inp()
        s = stdin.readline()
        c = s.count('0')
        one = n - c
        ans = one * c
        i = 0
        while i < n:
            ini = i
            while i < n and s[i] == s[ini]:
                i += 1
            ans = max(ans, (i - ini) ** 2)
        stdout.write(str(ans) + '\n')
main()