Богдан и подстроки

Назовем балансом строки разность между количеством вхождения в неё первого символа и другого символа. Тогда необходимо найти такую подстроку строки, в которой модуль баланса наибольший.

Посчитаем массив $$$bal[i]$$$ – баланс префикса данной строки $$$s$$$, заканчивающегося в позиции $$$i$$$. Тогда $$$bal[i] = bal[i - 1] + 1$$$, если $$$i$$$-й символ равен $$$1$$$-му, и $$$bal[i] = bal[i - 1] - 1$$$ иначе.

Теперь как по этому массиву быстро вычислить баланс некоторой подстроки исходной строки $$$s$$$. Пусть нам нужно определить баланс подстроки с $$$i$$$ по $$$j$$$. Если бы мы делали это проходом, мы бы начали с нуля и шли счетчиком как в предыдущем абзаце. Вместо этого, давайте просто посмотрим как изменится баланс, от позиции $$$i-1$$$ (предположили, будто бы на тот момент баланс 0), к позиции $$$j$$$. Эта величина равна $$$bal[j] - bal[i-1]$$$ и равна балансу подстроки $$$i..j$$$.

Таким образом нам нужно найти такие i и j, что $$$bal[j] - bal[i]$$$ – максимальное. Это соответствует подстроке $$$i+1..j$$$. Нетрудно заметить, что для этого достаточно взять максимальный и минимальный элементы в массиве bal (учитывая, что $$$bal[0] = 0$$$).

Получили линейное относительно размера входных данных решение (посчитать балансы префиксов, и найти в этом массиве максимум и минимум).