Составим граф из всех букв и проведем ребра между разными буквами минимальной ценой замены. Посчитаем минимальное расстояние в графе изменений алгоритмом Флойда-Уоршелла за O(a³), где a — размер алфавита. Расстояние между вершиной a и b в графе соответствует минимальному количеству монет, которое нобходимо, чтоб получить из символа a символ b.

Рассмотрим делители n, только такие числа являются кандидатами на k-строку из n символов. Таких подходящих k будет порядка .

Будем решать для каждого k отдельно. Рассмотрим букву на позициях i, для каждого i mod k посчитаем количество букв стоящих на таких позициях. Решаем независимо для каждого остатка от деления на k. Для этого переберем букву, которая будет стоять на этих позициях и посчитаем суммарную цену замены на необходимую букву.