0

I encountered the following problem for which I couldn't quite find the appropriate solution.

The problem says for a given string having a specific hash value, find the lowest string (which is not the same as the given one) of the same length and same hash value (if one exists).

E.g. For the following value mapping of alphabets:
{a:0, b:1, c:2,...,z:25}
If the given string is: ady with hash value - 27. The lexicographically smallest one (from all possible ones excluding the given one) would be: acz

Solution approach I could think of:
I reduced the problem to Coin-Change problem and resorted to finding all possible combinations for the given sum. Out of all the obtained solutions, I sort them up and find the lowest (or the next smallest if the given string is smallest).
The problem however lies with finding all possible solutions (even in a DP approach) which might be inefficient for larger inputs.

My doubt is:
What solution strategy (possibly even Greedy) could give a better time complexity than above?

Aardavak
  • 1
  • 1

1 Answers1

0

I cannot guarantee that this will give you a lower complexity, but a couple of things:1 you don't need to check all the space, just the space of lexicographic value less than or equal to the given string. 2: you can formulate it as an integer programming problem:

Assuming your character space is the letters, and each letter is given its number index[0-25] so a corresponds to 0, b to 1 and so forth. let x_i be the number of letters in your string corresponding to index i. You can formulate your problem as:

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

Where wi= 26^i, ai is equal to hash(letter(i)), n is the number of letters of the original string, N is the hash value of the original string. This is an integer programming problem so you can try plugging it to a solver. The original problem is very similar to subset sum problem with fixed subset size (where the hash values are the elements you are summing over, and the subset size is the length of the string) so you might also want to take a look at that, although as you will see from the answer it is a complicated problem.

Juan Carlos Ramirez
  • 2,054
  • 1
  • 7
  • 22