Balanced Prefix

Difficulty: 1200 3000 ms 128 MB

strings prefix-sums

Print the length of the longest PREFIX containing equally many 0s and 1s (0 if none).

Input: one line with a binary string.

Output: the longest balanced prefix length.

Constraints:

• 1 ≤ |S| ≤ 10⁵

Sample Tests

110100

6

111

0

Read the Editorial