Построим граф из двух типов вершин: вершины строк и вспомогательные вершины вида $$$(c, k)$$$, где $$$c$$$ — буква, а $$$k$$$ — некоторое количество её вхождений. Для каждой строки $$$s_i$$$ и каждой буквы $$$c$$$, для которой $$$f(s_i, c)=k \gt 0$$$, добавим ребро между вершиной строки $$$i$$$ и вершиной $$$(c, k)$$$.

Переход из строки $$$s_i$$$ в строку $$$s_j$$$ по букве $$$c$$$ с одинаковым количеством $$$k$$$ соответствует пути $$$i \to (c, k) \to j$$$. Чтобы его стоимость была ровно $$$k$$$, каждому из двух рёбер дадим вес $$$k/2$$$. Тогда суммарная длина такого пути равна $$$k$$$, то есть ровно нагреву из условия.

После этого остаётся запустить алгоритм Дейкстры из вершины первой строки.