Strange Printer

Intuition

Printing s[j] can always be tacked on as its own fresh run, giving the baseline dp[i][j] = dp[i][j-1] + 1. The savings come when some earlier position k in the range shares the same character as s[j]: the run that prints s[k] can be extended rightward to also paint s[j] for free. In that case the interval splits into dp[i][k] (which already pays for the shared character) plus the untouched middle dp[k+1][j-1], and the print for s[j] is absorbed. We try every such matching k and keep the cheapest. Filling by increasing interval length ensures all smaller ranges are ready before we combine them.

Algorithm walkthrough

1. 1Let dp[i][j] be the minimum prints needed to produce the substring s[i..j]; set every single character dp[i][i] = 1.
2. 2Process i from right to left and j from i+1 upward so shorter intervals are already solved.
3. 3Start with dp[i][j] = dp[i][j-1] + 1, treating s[j] as an independent new run.
4. 4For each k in [i, j-1] with s[k] == s[j], extend s[k]'s run to cover s[j]: candidate = dp[i][k] + (k+1 <= j-1 ? dp[k+1][j-1] : 0).
5. 5Take the minimum over all such candidates, then return dp[0][n-1] for the whole string.

Implementation

class Solution:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n):
                dp[i][j] = dp[i][j - 1] + 1
                for k in range(i, j):
                    if s[k] == s[j]:
                        right = dp[k + 1][j - 1] if k + 1 <= j - 1 else 0
                        dp[i][j] = min(dp[i][j], dp[i][k] + right)
        return dp[0][n - 1]