Problem statement

https://leetcode.com/problems/strange-printer/

Solution

Very difficult problem indeed, similar to Problem 0546 Remove Boxes and a bit to Problem 0312 Burst Balloons. Let dp(i, j) be the minimum number of turns to print symbols from i to j. Then it can be shown that we need to find all symbols in this string equal to s[i] and evaluate dp(i, k-1) + dp(k+1, j) another option is to type first symbol and use dfs(i + 1, j) + 1 number of moves.

Sketch of proof:

  1. It is always more optimal for l[i:j+1] string on the first move fill it with s[i]. The idea is that only one print that prints s[l] on place l, imagine that it is print number x. Then we can rearrange prints in such way that our print will be the first (it is not obvious, may be more details needed).
  2. Let us find in range l ... r such element p (pivot), which was not changed after the first move. We will take the rightmost such element. If such element exists, we can say that all problem can be divided into two subproblems l ... p - 1 and p + 1 ... r, because after the first move, element p is not changed. So, does not matter, in which order we deal with this problems, we can always rearrange them in such way that we first solve one subproblem and then another. If we do not have pivot, it means, that all elements were changed - but except the first one (because if it was changed as well, first move can be removed), it this case we look at dfs(i + 1, j) + 1.

Complexity

It is O(n^3) for time and O(n^2) for space.

Code

class Solution:
    def strangePrinter(self, s):
        @lru_cache(None)
        def dp(i, j):
            if i > j: return 0
            cand = dfs(i+1, j) + 1
            for k in range(i+1, j+1):
                if s[k] == s[i]:
                    cand = min(cand, dp(i, k-1) + dp(k+1, j))
            return cand
                
        return dp(0, len(s) - 1)