821. Strange Printer
A sign maker owns an odd label printer. In one turn it prints one chosen letter over a contiguous block of positions of an initially blank strip, and every position in the block takes that letter, overwriting what was there before. Printing is allowed over already printed positions as often as you like.
Given the target string s, return the minimum number of turns needed so that the strip reads exactly s. The empty string needs 0 turns.
Aim for time O(n^3) in the worst case and space O(n^2), where n is the length of s.
Example 1
- Input:
- s = "pqrqp"
- Output:
- 3
- Explanation:
Print a run of p across all five slots, then q over the middle three, then r in the centre: 3 turns.
Example 2
- Input:
- s = "mnnmoomn"
- Output:
- 4
- Explanation:
Print m over the first seven cells, then n over cells 2-3, then o over cells 5-6, and finally n on the last cell: 4 turns.
Constraints
0 ≤ s.length ≤ 300
s consists of lowercase English letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n^3)
- Space
- O(n^2)