# Speeding up the Rummikub algorithm - explanation required

Regarding this question: Rummikub algorithm.

I was reading the first part of the solution in the posted answer (specifically, when there are no jokers involved, all tiles are distinct and only four colours are involved). Then, I reached the part in which the says that the algorithm runs in $$O(ABCD(A+B+C+D))$$ time, which is easy to determine why.

However, he the goes on to saying that we can speed up the algorithm so as to run in $$O(ABCD)$$ time by changing "the recurrence to ensure this occurs only once while maintaining correctness, which leads to $$O(1)$$ time for every 'cell' in the DP-table".

My problem is: I do not see how this can be done. I have tried playing around a bit with the recurrence, but I do not see how it can be modified, or what else we should keep track of so that we can speed up the time.

Can someone please give me a hint/explanation on how this can be done?

• I must confess that the answer I wrote is not entirely correct: I don't know how to do this with only one check, but I can do it with 3, which is still a constant and is fine. For a hint: note that any run of length at least 6 can be split into more runs. Then, do we really need to look for runs of length larger than 5? Sep 27, 2020 at 14:28