Задача с собеседования в Яндекс.
Дается строка s которая состоит из нулей и единиц. Вы должны удалить ровно одно число из строки таким образом, чтобы максимальная по длине подстрока состоящая из одинаковых чисел была максимальной.
Например:
s = 110111011100
ответ 6
Решение:
Давайте зафиксируем позицию i которую удалим. Очевидно в оптимальном ответе выгодно удалять такую позицию, что подстрока будет содержать позицию i. Таким образом вы должны найти максимальное количество 1/0 справа от i и слева от i. Пусть количество 1 справа равно r1, а количество единиц слева l1. Аналогично r0 и l0 для нуля. Тогда вы должно обновить свой ответ от max(r0+l0, r1+l1).

Весь вопрос как найти r0,r1,l0,l1.
Давайте научимся находить r0, r1, для каждой позиции.
Для этого пройдемся справа налево по строке. Если s[i]=1 то сделаем r1[i]=r1[i+1]+1, r0[i]=0, а если s[i]=0 сделаем r0[i]=r0[i+1]+1, r1[i]=0.

После аналогичным образом посчитаем l0, l1 (двигаясь слева направо)

Тогда ответом будет
max (max(l0[i-1]+r0[i+1], l1[i-1]+r1[i+1])) по всем i.

Время работы О(N)