0664. Strange Printer¶
题目信息¶
- 题号:
0664
- 难度:
Hard
- 主题:
字符串、区间打印、覆盖、最少轮次
- 原题:
- 重点:
每轮只能打印一种字符但区间长度任意、后续打印可以覆盖旧字符、目标是从空白纸得到完整字符串
题目重述¶
一台打印机初始面对一段空白区域。每次打印可以选择一种字符,并把它打印到任意一个连续区间的所有位置;之后的打印可以覆盖先前位置上的字符。
给定只包含小写英文字母的非空字符串 s,返回从空白状态最终得到 s 所需的最少打印次数。一次操作只能使用一种字符,但同一种字符可以在不同操作中再次打印。s.length 位于 [1, 100]。
自建示例¶
先打印大区间再覆盖中间:
输入:s = "aba"
输出:2
解释:先在三个位置打印 "aaa",再把中间位置覆盖为 b,即可用两次打印得到目标。
多层覆盖:
输入:s = "abcba"
输出:3
解释:可以依次打印 "aaaaa"、在中间三个位置打印 b、再把正中位置打印为 c,共三次。