Найти лексикографически наименьшую строку с заданным значением хеша [Competitive Coding]

Question

Я столкнулся со следующей проблемой, для которой не смог найти подходящего решения.

Проблема говорит, что для заданной строки, имеющей определенное значение хеш-функции, найдите самую нижнюю строку (которая не совпадает с заданной) из одинаковой длины и одинакового хеш-значения (если оно существует).

Например. Для следующее сопоставление значений алфавитов:
{a: 0, b: 1, c: 2, ..., z: 25}
Если заданная строка: ady с хеш-значением - 27. лексикографически наименьший (из всех возможных, исключая данный) будет: acz

Подход к решению, о котором я мог подумать:
Я свел задачу к проблеме замены монет и прибег к поиску всех возможных комбинаций для данной суммы. Из всех полученных решений я сортирую их и нахожу самое низкое (или следующее самое маленькое, если данная строка самая маленькая).
Проблема, однако, заключается в поиске всех возможных решений (даже в подходе DP), которые могут быть неэффективными для больших входов.

Мои сомнения :
Какая стратегия решения (возможно, даже Greedy) может дать лучшую сложность времени, чем выше?

Answer 1

Я не могу гарантировать, что это даст вам меньшую сложность, но пару вещей: 1 вам не нужно проверять все пространство, только пространство лексикографического значения меньше или равно данной строке.2: вы можете сформулировать это как задачу целочисленного программирования:

Предполагая, что вашим символьным пространством являются буквы, и каждой букве присваивается свой числовой индекс [0-25], так что a соответствует 0, b - 1 и т. Д.вперед.пусть x_i будет количеством букв в вашей строке, соответствующих индексу i.Вы можете сформулировать свою проблему следующим образом:

min sum_i(wi*xi)
st xi*ai = M
xi>=0,
sum_i(xi)=n
sum_i(wi*xi)<= N
xi integer

Где wi= 26^i, ai равно hash(letter(i)), n - количество букв исходной строки, N - хеш-значениеоригинальная строка.Это целочисленная проблема программирования, поэтому вы можете попробовать подключить ее к решателю.Исходная задача очень похожа на проблему суммы подмножеств с фиксированным размером подмножества (где значения хэша - это элементы, по которым вы суммируете, а размер подмножества - длина строки), так что вы можете также захотетьвзгляните на это, хотя, как вы увидите из ответа, это сложная проблема.