What is the main strategy for solving Strange Printer efficiently?

Use state transition dynamic programming to compute minimum turns for all substrings and merge overlapping character sequences.

Why do we consider all partitions within substrings?

To correctly apply DP transitions, we must examine every possible split to minimize the total printing turns while leveraging character overlaps.

Can the printer overwrite existing characters without extra turns?

Yes, this property allows merging operations and reduces the number of total turns in dynamic programming solutions.

What is the time complexity for this approach?

O(n^3), because we evaluate O(n^2) substrings and for each substring consider O(n) partition points.

Is Strange Printer always solvable with DP for strings up to length 100?

Yes, the DP approach handles up to 100 characters efficiently, respecting the problem's constraints on string length.

#664

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

奇怪的打印机

有台奇怪的打印机有以下两个特殊要求：打印机每次只能打印由同一个字符组成的序列。每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。示例 1：输入： s = "aaabbb" 输出： 2 解释： …

字符串动态规划

题目描述

有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印由 同一个字符 组成的序列。
每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。

给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

示例 1：

输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa" 然后打印 "bbb"。

示例 2：

输入：s = "aba"
输出：2
解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。

提示：

1 <= s.length <= 100
s 由小写英文字母组成

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示打印完成区间 $s[i..j]$ 的最少操作数，初始时 $f[i][j]=\infty$ ，答案为 $f[0][n-1]$ ，其中 $n$ 是字符串 $s$ 的长度。

考虑 $f[i][j]$ ，如果 $s[i] = s[j]$ ，那么我们在打印 $s[i]$ 时可以顺便打印 $s[j]$ ，这样我们即可忽略字符 $s[j]$ ，在区间 $s[i+1..j-1]$ 内继续进行打印。如果 $s[i] \neq s[j]$ ，那么我们需要分别完成该区间的打印，即使用 $s[i..k]$ 和 $s[k+1..j]$ ，其中 $k \in [i,j)$ 。于是我们可以列出如下的转移方程：

f[i][j]= \begin{cases} 1, & \textit{if } i=j \\ f[i][j-1], & \textit{if } s[i]=s[j] \\ \min_{i \leq k < j} \{f[i][k]+f[k+1][j]\}, & \textit{otherwise} \end{cases}

在枚举时，我们可以从大到小枚举 $i$ ，从小到大枚举 $j$ ，这样可以保证在计算 $f[i][j]$ 时，状态 $f[i][j-1]$ 和 $f[i][k]$ 以及 $f[k+1][j]$ 都已经被计算过。

时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

speed

复杂度分析

指标	值
时间	complexity is O(n^3) because for each of the O(n^2) substrings, we consider O(n) partitions. Space complexity is O(n^2) to store DP states for all substring combinations.
空间	O(n^2)

psychology

面试官常问的追问

外企场景

question_mark
Are you considering repeated characters for merging print operations?
question_mark
Can you explain your DP state definition and transitions clearly?
question_mark
How do you handle overlapping substrings to minimize redundant turns?

warning

常见陷阱

外企场景

error
Ignoring character overlaps, leading to overcounting turns.
error
Incorrect DP state transitions that don't merge adjacent matches.
error
Starting from wrong substring lengths, breaking subproblem dependency order.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing the printer to print any substring of consecutive different characters in one turn.
arrow_right_alt
Counting minimum turns if the printer can print reversed substrings.
arrow_right_alt
Optimizing for strings with only two unique characters repeatedly alternating.

help

常见问题

外企场景

继续练习

#678 有效的括号字符串 #647 回文子串 #639 解码方法 II