Почему не все тестовые задания одинаково полезны: разбор одного фееричного провала

Можно держать массив следующих точек (и отдельно прошлых). Заранее посчитать, как-то так:

_nextAllowedPoints = new short[_allowedPoints.Length];
short lastPoint = -1;
for (short i = (short)(_allowedPoints.Length - 1); i >=0; i--)
{
   if (_allowedPoints[i])
   {
      lastPoint = i;
      _nextAllowedPoints[i] = 0;
   }
   else if (lastPoint < 0)
   {
      _nextAllowedPoints[i] = lastPoint; // -1
   }
   else
   {
      _nextAllowedPoints[i] = (short)(lastPoint - i);
   }
}

АТАТА: распутываем задачу про палиндром

или log|W|, где W максимальная подстрока и если W<|Е|. Но так как нужны только входные параметры то W=O(n). и правильный фактор O(log(min(n,|Е|))).
Результат O(n*log(min(n,|Е|)))

АТАТА: распутываем задачу про палиндром

Ок, теперь картина проясняется. Если мы хотим находить самый частый элемент при каждом сдвиге «окна» то нам понадобится структура данных для получения самого частого символа — куча (или другая очередь приоритетов). И так как понадобится каждый шаг делать операций добавки и удаления то это добавит фактор O(log|E|). И решение будет O(n*log|E|). Конечно, в теорий, при |Е| константе можно и пренебречь, но при увеличение алфавита (E) или при наивной имплементаций нахождения максимума, код будет бежать очень медленно.

АТАТА: распутываем задачу про палиндром

Не понятно… Выбор максимальных элементов происходит А. отдельно для чётных и нечётных Б. Перед второй стадий алгоритма В. Из всей первоначальной строки.
Поэтому: В первом случае (ZYXAWA) мы к примеру разыграли Z («если символов с максимальным числом вхождений несколько, то можно выбрать любой») и A. То получается сначала ZAxawa, потом zAХawa, zyZAwa, zyxAZA — самая длинная подстрока из 3 символов. А правильно 4.

Со вторым примером всё хуже, максимальные символы это S и Z. А менять то надо Y или A.

АТАТА: распутываем задачу про палиндром

А почему алгоритм верный? Нету ли тут проблемы с выбором (максимального) элемента на замену?
К примеру ZYXAWA и одно изменение, должно давать подстроку длиной в 4 XAWA=>WAWA или XAXA. А с этой эвристикой не понятно что получается (если выберет Z).
Или AYAXABCSZEFGHIZJKLMNZOPQRSZ, здесь максимальные элементы это S (2 раза) и Z (4 раза). А правильная подстрока с одним изменением AYAYA.