Strange Printer

Image by SweetMellowChill from Pixabay

In this article, I’ll explain in detail the solution for the “Strange Printer” coding problem. It’s featured on multiple coding exercise websites, you may have encountered it at LeetCode by the number of 664.

Problem description

Suppose you have a printer whose purpose is to generate a string of lowercase English characters. The limitation of the printer is that at each step, it can only print a string containing the same character, e.g. aaa, b, or cccc.

The trick is that the printer doesn’t print out the steps in sequence, but rather can start printing at any place, possibly overwriting the results of the previous steps, e.g.:

Step 1: aaaaa
Step 2:  bbb
Step 3:   c
Result: abcba

Another example:

Step 1: aaa
Step 2:    bbb
Result: aaabbb

It’s easy to see that such printer may produce any possible string of lowercase English characters, given enough steps. In the worst case, it can simply print the characters one-by-one in sequence, for instance:

1: a
2:  b
3:   c
   abc

You are given a string, e.g. abcba, and you need to find the minimum amount of steps for the printer to generate it.

Designing the algorithm