\textbf{ Подгруппа 1 ($n \leq 10, k \leq 2$). }

В этой подзадаче можно было перебрать все возможные варианты расшифровки (для каждой позиции выбрать, какую из двух букв мы возьмём) для каждого варианта определить его информативность и выбрать оптимальную расшифровку. Информативность строки можно найти, честно перебрав $d$ и проверив, верно ли, что $s$ представляет собой префикс длины $d$, повторённый $\frac{n}{d}$ раз. Такую проверку можно осуществить за $O(n)$, при этом проверять имеет смысл только те $d$, которые являются делителями $n$. Поскольку делителей $n$ не более чем $2 \sqrt{n}$, то нахождение информативности будет работать за $O(n \sqrt{n})$. Всего существует $k^n$ различных вариантов расшифровок, поэтому общая асимптотика алгоритма --- $O(k^n n \sqrt{n})$.

\textbf{ Подгруппа 2. }

В этой подзадаче можно было заметить, что оптимальной будет расшифровка, содержащая только буквы \texttt{a} и \texttt{c}. Действительно, ведь при такой расшифровке буквы совпадают на всех парах позиций, на которых они вообще могли бы совпасть, поэтому информативность в таком случае будет минимально возможной. Построить требуемую расшифровку можно за $O(nk)$.

\textbf{ Подгруппа 3 ($k \leq 3$). }

Давайте, как в первой подзадаче, будем перебирать $d$ (делитель $n$) и проверять, можем ли мы получить строку с информативностью $d$. Для этого для каждого $1 \leq i \leq d$ надо проверить, что у позиций $i, i+d, i+2d, \dots$ существует общая буква. Для этого переберём букву на позиции $i$ и проверим, что на позициях $i+d, i+2d, \dots$ эта буква также присутствует. Для позиции $i$ проверку можно осуществить за $O\left(\frac{n}{d} \cdot k^2\right)$, для всех $i$ это будет работать за $O(n k^2)$. Суммарно по всем $d$ алгоритм будет работать за $O(n \sqrt{n} k^2)$. При аккуратной реализации с break такое решение может заходить на 100 баллов.

\textbf{Полное решение.}

Идея: давайте для каждой позиции вместо $k$ букв, которые на ней стоят, будем хранить массив длины 26, в котором для каждой буквы записано, присутствует она на этой позиции или нет. Теперь для каждого $i$ мы можем за $O\left(26 \cdot \frac{n}{d}\right)$ проверить, что на позициях $i, i+d, i+2d, \cdot$ есть общая буква (перебрать одну из букв на позиции $i$ и за $\frac{n}{d}$ проверить, что она подходит). Таким образом, общая асимптотика алгоритма составит $O(26 \cdot n\sqrt{n})$.