Search code examples
algorithmdynamic-programminggreedy

Dynamic programming approach or a case that fails the greedy

I have a string of length 1 <= |S| <= 100 and K (1 <= K <= 10)

This string contains digits < K and question marks. I want to replace these question marks with digits < K, no two neighboring digits being equal. The string is circular so it can't be like this: 1?1 or 11?.

The resulting string must be lexicographically the smallest one.

Example input and output

input:
K = 4
string = ?????

output:
01012

I've tried a greedy approach but it fails for some unknown testcases. I think it needs a dp approach but couldn't figure out the states, and a pure recursion code won't fit in time.

Any help for the dp approach, or tricky test cases that fail the greedy?

Thanks,

Solution

  • If you have a digit at one end of string, the greedy algorithm will give you the right answer.

    If your string starts and ends with a question mark, you have 2 possibilites for the first character (0 or 1), run the greedy algorithm on both cases and take the best.

    Wrong answer as pointed out by Likao:

    The greedy works but you must start with the first question mark which is just after a known digit.