Strange Printer - LeetCode 664 - Python

Solution, explanation, and complexity analysis for LeeCode 664, the problem of the day for July 30th, in Python.

[chrisgu]

Just my intuition from what you have explained so far correct me if I am wrong. So for printer(i, j) it returns the minimal number of operations needed to print characters from [i, j]. In the for loop you are splitting whenever we see a matching character with our start character in the remaining string form [i + 1, j]. In that case we know that we could possibly achieve a lower number of operations for printing the first part [i, k].

The reason why we pass in dp(i, k - 1) is because when we have matching characters we are assuming that at index i we are already printing a sequence of similar character from i until index k inclusive. (i.e. "aba", when 0 == 2, at that instance we assume that we printed 'aaa' already, we actually only really consider the cost of printing 'ab' -> when we print 'a' -> 'aaa' and then when we print 'b' we are actually replacing the middle 'a' -> 'aba'.

[evgeniybarykin]

That's a really great explanation! The only part I'm a bit confused about is why this algorithm correctly handles strings where there are groups of letters in the middle of the string that are the same as the first letter. For example, "abaac".

[vishaalkumaranandan]

Please use dark mode next time
It is just hurting my eyes