0664. Strange Printer

题目信息

题号:

0664

难度:

Hard

主题:

字符串、区间打印、覆盖、最少轮次

原题:

LeetCode 0664

重点:

每轮只能打印一种字符但区间长度任意、后续打印可以覆盖旧字符、目标是从空白纸得到完整字符串

题目重述

一台打印机初始面对一段空白区域。每次打印可以选择一种字符,并把它打印到任意一个连续区间的所有位置;之后的打印可以覆盖先前位置上的字符。

给定只包含小写英文字母的非空字符串 s,返回从空白状态最终得到 s 所需的最少打印次数。一次操作只能使用一种字符,但同一种字符可以在不同操作中再次打印。s.length 位于 [1, 100]。

自建示例

先打印大区间再覆盖中间:

输入:s = "aba"
输出:2
解释:先在三个位置打印 "aaa",再把中间位置覆盖为 b,即可用两次打印得到目标。

多层覆盖:

输入:s = "abcba"
输出:3
解释:可以依次打印 "aaaaa"、在中间三个位置打印 b、再把正中位置打印为 c,共三次。