Детская железная дорога

В ходе решения задачи и её дальнейшего изучения написал множество решений. Одно из тех решений, что прошли все тесты, выдаёт неправильный ответ для строки "ABCABCABAC", а другое (которое занимает второе место в рейтинге) не укладывается по времени на тесте "AZ"*249999+"AY" (иными словами строка максимальной длины, в которой чередуются буквы A и Z, но вместо последней Z стоит Y). Было бы неплохо, если бы эти тесты добавили к задаче, ибо на данный момент есть основание полагать, что большинство производительных решений из рейтинга работают корректно только из-за слабого покрытия тестами.

Также интересно узнать, существует ли решение за O(N) с учётом этих тестов, или же быстрее, чем за O(N*log(N)) задача не решается.