Problem

There is a strange printer with the following two special properties:

  • The printer can only print a sequence of the same character each time.
  • At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.

Given a string s, return the minimum number of turns the printer needed to print it.

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

Example 1:

Input: s = “aaabbb”
Output: 2
Explanation: Print “aaa” first and then print “bbb”.

Example 2:

Input: s = “aba”
Output: 2
Explanation: Print “aaa” first and then print “b” from the second place of the string, which will cover the existing character ‘a’.

Constraints:

  • 1 <= s.length <= 100
  • s consists of lowercase English letters.

Test Cases

1
2
class Solution:
    def strangePrinter(self, s: str) -> int:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('s, expected', [
    ("aaabbb", 2),
    ("aba", 2),

    ("baacdddaaddaaaaccbddbcabdaabdbbcdcbbbacbddcabcaaa", 19),
])
@pytest.mark.parametrize('sol', [Solution(), Solution2()])
def test_solution(sol, s, expected):
    assert sol.strangePrinter(s) == expected

Thoughts

对于一个下标区间 [i, j]（0 ≤ i ≤ j < n），看如何打印对应的子字符串 s[i..j]（为了方便，用 s[i..j] 表示 s[i:j+1]）。

如果 i = j，显然需要打印一次 s[i]。下边看 i < j 的情况。

最简单办法就是先打印 s[i]，然后打印剩余的部分即 s[i+1..j]。

如果 s[j] = s[i]，那么跟打印 s[i..j-1] 没区别。

如果区间内还有一个下标 k，i < k < j，s[k] = s[i]，那么可以先打印 s[i..k]，再打印 s[k+1..j]。而其中 s[i..k] 部分跟 s[i..k-1] 的打印次数是一样的。对所有可能的 k 进行枚举，而如果 s[j] = s[i]，可以把 j 也当作特殊的 k 去处理。

定义 dp(i, j) 表示打印 s[i..j] 所需的最少次数。

{dp(j,i)=0dp(i,i)=1dp(i,j)=min⁡k{1+dp(i+1,j)dp(i,k−1)+dp(k+1,j)for s[k]=s[i]\begin{cases} dp(j,i)=0 \\ dp(i,i)=1 \\ dp(i,j)=\min_k\begin{cases} 1+dp(i+1,j) \\ dp(i,k-1)+dp(k+1,j) & \text{for }s[k]=s[i] \end{cases} \end{cases}

注意边界情况。

时间复杂度大约 O(n³)，空间复杂度 O(n²)。

Code

Iteratively

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from bisect import bisect_left


class Solution:
    def strangePrinter(self, s: str) -> int:
        min2 = lambda a, b: a if a <= b else b
        ss: list[int] = [] # `ss` is `s` without consecutive identical characters.
        occurs: list[list[int]] = [[] for _ in range(26)] # occurs[char]: char's occurrences in ss
        prev = ''
        for c in s:
            if c == prev: continue
            val = ord(c) - 97
            occurs[val].append(len(ss))
            ss.append(val)
            prev = c

        n = len(ss)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1

        for size in range(2, n + 1):
            for i in range(n - size + 1):
                j = i + size - 1
                dp[i][j] = 1 + dp[i+1][j]
                if ss[j] == ss[i]: dp[i][j] = min2(dp[i][j], dp[i][j-1])

                occ = occurs[ss[i]]
                for k in occ[bisect_left(occ, i)+1:]:
                    if k >= j: break
                    dp[i][j] = min2(dp[i][j], dp[i][k-1] + dp[k+1][j])

        return dp[0][n-1]

Recursively

solution2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from bisect import bisect_left
from functools import cache


class Solution:
    def strangePrinter(self, s: str) -> int:
        min2 = lambda a, b: a if a <= b else b
        ss: list[int] = [] # `ss` is `s` without consecutive identical characters.
        occurs: list[list[int]] = [[] for _ in range(26)] # occurs[char]: char's occurrences in ss
        prev = ''
        for c in s:
            if c == prev: continue
            val = ord(c) - 97
            occurs[val].append(len(ss))
            ss.append(val)
            prev = c

        @cache
        def dfs(l: int, r: int) -> int:
            if l >= r: return 0
            elif l == r - 1: return 1

            min_cnt = 1 + dfs(l+1, r)

            occ = occurs[ss[l]]
            for k in occ[bisect_left(occ, l)+1:]:
                if k >= r: break
                min_cnt = min2(min_cnt, dfs(l, k) + dfs(k+1, r))

            return min_cnt

        return dfs(0, len(ss))
hard
参考资料
许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~