Strange Printer
Hard · Dynamic Programming · String · Dynamic Programming
Problem
A strange printer works by two rules:
- Each turn it prints a run of one repeated letter.
- The run may start and end anywhere, and it covers whatever was printed there before.
Given a string s, return the fewest turns the printer needs to print it.
Examples
Input: s = "abcabc" Output: 5
For example: "aaaa" over positions 0 to 3, then b, c, b and c one at a time. No plan uses fewer than 5 turns.
Input: s = "aaaa" Output: 1
One run prints the whole string.
Input: s = "abab" Output: 3
Print "aaa" over positions 0 to 2, then a b at position 1 and another at position 3.
Constraints
- 1 <= len(s) <= 100
- s consists of lowercase English letters
Approaches
- Memoized recursion on the raw string — time O(n³), space O(n²) cache plus O(n) recursion
Follow-up
Run the printer backward and every turn becomes a deletion of one block of equal letters, after which the neighbors close up. The fewest deletions that clear the string equal the fewest turns that print it; see the use case "Erase a string in blocks of one letter".
Related problems
Start free on Cariara · Coding problems · System design studio
