Прекрасно понимаю, что на другом языке отвечать такое себе занятие, но так уж получается.

Эту задачу можно решить детерминировано за 26*log(n)*n, а вероятностно можно улучшить до 26*n, теперь давайте поймем как решать. Возможно, что есть что-то лучше, но я не придумал, если кто-то придумает, расскажите, пожалуйста, очень интересно.

Решение:

План решения следующий: 1. перебираем правую (R) границу отрезка
2. пытаемся найти самую левую (L) границу при заданном R

мы можем поддерживать массив (cnt_a, cnt_b, ..., cnt_z), где cnt_i — количество букв i на префиксе [1...R]. При 1-индексе и R = 0 будет (0, 0, ..., 0)

теперь мы хотим найти на префиксе такое L' с его массивом (cnt_l_a, cnt_l_b, ...), что будет выполнено:

cnt_i — cnt_l_i = Const

то есть cnt_l_i = cnt_i — Const, значение Const мы не знаем, однако мы можем сделать "нормировку", а именно возьмем Const таким, чтобы оно было как можно больше и cnt_l_i >= 0, при этом обязательно будет j, что cnt_l_j = 0, и разумеется Const = min(cnt). Если мы будем сохранять постепенно нормированные массивы, то нам достаточно будет выбрать один из них или убедиться, что таких нет.

Реализация (c++ стиль):

(cnt_a, ...) = vector

множество векторов map<vector, int> — [(нормированный массив), (первый префикс с заданным нормированным массивом)]

изначально в map кинем нулевой вектор и присвоим значение 0, а далее постепенно будем идти вправо, временно нормировать наш массив, смотреть в map, а далее обновлять map и наш массив.

Сложность: n раз в map, где ключи сравниваются за размер алфавита, то есть за 26, получаем 26*logn*n.

Ускорение:

Это можно быстрее, если сохранять множества (cnt_a, ...) в виде хешей x^cnt_a + .. + x^cnt_z mod H (18 пункт), тогда за 26 операций построим нормированный массив. Теперь все наши массивы превращены в числа, вместо map воспользуемся unordered_map и получим ожидаемое O(1) на обращение. Таким образом получили O(|Алфавит| * n)!

p.s. если где-то есть ляпы и описки, поправляйте, поправлю

upd1. первый нашел, неверно считал хеши нормированного массива простым вычитанием, и думал, что получится O(n)

https://codeforces.com/blog/entry/95004?#comment-840439

nevermind