hardDynamic Programming 2DPure DSA~42 min
Fewest Printer Passes to Render a Banner
A peculiar printer prints one contiguous run of a single character per pass, and a later pass can overwrite part of an earlier run. Find the minimum number of passes to produce a target string.
Problem
There is a strange printer that can only print a sequence of the same character each turn, and can print new characters over existing ones starting and ending at any position. Given a string s, return the minimum number of turns the printer needs to print it.
Input
A string s of length [1, 100], lowercase English letters.
Output
An integer: the minimum number of printing turns.
Constraints
- 1 <= s.length <= 100
- s consists of lowercase English letters.
Examples
Example 1
Input
s = "aaabbb"
Output
2
Print 'aaa' then 'bbb'.
Example 2
Input
s = "aba"
Output
2
Print 'aaa', then overwrite the middle with 'b'.