Strange Printer — Interval DP

Problem

A printer can only print same-character runs each turn. Find minimum turns to print string s.

Approach — Interval DP

dp[i][j] = min turns for substring s[i..j].

Base: dp[i][i] = 1
If s[i] == s[j]: save one turn → dp[i][j] = dp[i][j-1]
Try all splits: dp[i][j] = min(dp[i][k] + dp[k+1][j])

Time: O(n³) | Space: O(n²)

Solutions

Python

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

Complexity

Time: O(n³) | Space: O(n²)