Просто по длине слова определяем,  какой у нас случай.
(Замена,  удаление или вставка).

Затем для каждой позиции пытаемся внести изменения и смотрим,  получается у нас выполнение условия или нет.

Удобно завести массив постфиксных сумм для того чтобы быстро пересчитать сумму позиций единиц.