@solocaptain It looks like DP O(mnk) solution will visit many unnecessary sub-problems. I can't give a strict proof that how many unnecessary sub-problems it visited, but we can see an example: string one is 911111111119, and string two is 911111111119, and we are looking for a four-digit max number. The answer is 9999. But if we use DP, then we consider lots of unnecessary sub-problems like (11111111119,11111111119,4), etc. So we can try greedy method. In conclusion, DP method is correct, but the method had visited lots of unnecessary sub-problems, so it's a better idea to try greedy method after you have a DP method.