# Strange Printer

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

A good intuitive guess would be that we have to **reduce the problem somehow to problems of smaller size**, e.g. by considering substrings of the initial string and joining the results.

In other explanations, you may find the words “dynamic programming” right at the beginning — don’t bother with this for now, this is just an optimization technique that I’ll cover in the **“Optimizations”** section. For starters, let’s produce a “naïve” algorithm that simply finds the right solution, at whatever cost.

First, let’s call our algorithm `sp()`

and notice a couple of things:

- If we have a string of just one character, e.g.
`a`

, we only need one step to print it, so`sp("a") = 1`

. - For a two-character string, the result would be 1 if the characters are equal and 2 if they differ:
`sp("aa") = 1`

,`sp("ab") = 2`

. - For a string consisting of all-different characters, e.g.
`abcde`

, the number of steps would be equal to the length of the string, so`sp("abcde") = 5`

:

`1: a`

2: b

3: c

4: d

5: e

abcde

- Let’s generalize the previous observation: if a string starts from a character that doesn’t occur in the rest of the string, e.g.
`acbc`

, then we can print this character on step 1 and print the rest of the string on subsequent steps, reducing the problem to a smaller one:`sp("acbc") = 1 + sp("cbc")`

. We’ll call this the “worst-case solution”:

`1: a`

2: ccc

3: b

acbc

- However, if the first character of the string occurs in the rest of the string, we might have a better solution. We can first print a long string consisting of the first letter, and then print everything else on top and to the right of it. For instance, using the worst-case solution for
`abac`

would produce 4, but it could actually be printed in 3 steps. Let’s call this approach a “better solution”:

`1: aaa <- printing a long enough sequence of "a"`

2: b <- printing on top

3: c <- printing to the right

abac

- It should be easy to see from the above example how we could reduce the “better solution”. Let’s first split the
`abac`

string in`aba`

and`c`

. Let’s also note that the amount of steps for`aba`

would be the same as for`ab`

, so we could drop the last character, reducing the problem to`sp("ab") + sp("c")`

. - The first character could occur in multiple places throughout the string, so to get the minimum number of steps, we have to consider them all.

Let’s now try to write a “naïve” version of the algorithm that should at least work, maybe not in a very optimal way. As an input, we’ll give it a string `s`

, an int `i`

as beginning index and an int `j`

as the last index of a substring, inclusive:

`public int sp(char[] s, int i, int j) {`

if (i > j) {

return 0;

}

int firstLetter = s[i];

// worst-case solution

int answer = 1 + sp(s, i + 1, j);

// try to find a better solution

for (int k = i + 1; k <= j; k++) {

if (s[k] == firstLetter) {

// found the letter in the rest of the string

int betterAnswer = sp(s, i, k - 1) + sp(s, k + 1, j);

answer = Math.*min*(answer, betterAnswer);

}

}

return answer;

}

When running the algorithm for the first time, we ‘ll call it as follows:

`public int strangePrinter(String s) {`

return sp(s.toCharArray(), 0, s.length() - 1);

}

**The provided solution works**, but you may notice that it’s very slow on long strings. E.g. running it on a string `baacdddaaddaaaaccbddbcabdaabdbbcdcbbbacbddcabcaaa`

on my machine takes so much time I didn’t care to run the calculations till the end.

# Optimizations

## Memoization

You may notice that we split the string into smaller strings and do the calculations for them, but those calculations definitely overlap. We calculate the minimum step value for the same substring multiple times. This is a tell-tale sign that we need to apply Dynamic Programming.

This is a very broad concept, but here we can apply it as follows. Let’s just cache the result for each substring. Whenever we need to calculate the result for it, we look it up in the cache instead. Such technique is also called “memoization”, so we’ll call our cache `memo`

.

This `memo`

cache will be represented as a `n*n`

matrix, or a two-dimensional array, where `memo[i][j]`

cell would store the number of steps you need to print a substring `string[i..j]`

, indexes inclusive. This means e.g. that `memo[0][0]`

will be 1, since you need just 1 step to print a single letter — same for `memo[1][1]`

and for all other numbers on the main diagonal of the matrix.

Let’s store this cache in a field of the solution class, as well as the initial `array`

, to simplify the recursive code calls:

private int[][] memo;private char[] array;public int strangePrinter(String s) {

if (s.isEmpty()) {

return 0;

} int N = s.length();

memo = new int[N][N]; array = s.toCharArray(); return sp(0, s.length() - 1);

}

Then the recursive method `sp`

could be rewritten to take advantage of the `memo`

cache:

`public int sp(int i, int j) {`

if (i > j) {

return 0;

}

if (memo[i][j] == 0) {

int firstLetter = array[i];

int answer = 1 + sp(i + 1, j);

for (int k = i + 1; k <= j; k++) {

if (array[k] == firstLetter) {

int betterAnswer = sp(i, k - 1) + sp(k + 1, j);

answer = Math.*min*(answer, betterAnswer);

}

}

memo[i][j] = answer;

}

return memo[i][j];

}

This is a very slight change, but it brings a ton of performance improvement. This algorithm is actually O(n³) time complexity, since we need to populate the n*n size table, and for each element of the table we need to do a `[i..j]`

loop to calcualte it. The space complexity is O(n²), since this is the number of cells in the`memo`

matrix.

## Squashing the initial string

Another improvement would be to reduce the initial string by removing all repeating characters. If you think of it, this doesn’t change the number of steps to get to the solution, since writing `a`

and writing `aaa`

would both take exactly one step. Let’s implement the `squash`

method to do this:

`char[] squash(String s) {`

char[] chars = s.toCharArray();

int last = 0;

int fullLength = chars.length;

for (int i = 1; i < fullLength; i++) {

if (chars[i] != chars[last]) {

chars[++last] = chars[i];

}

}

return Arrays.*copyOf*(chars, last + 1);

}

## Reducing the memo matrix

We could also do with the half of required space, by storing only the upper half of the matrix:

`int N = array.length;`

memo = new int[N][];

for (int i = 0; i < N; i++) {

memo[i] = new int[N];

}

## Pre-calculating the trivial values

Finally, pre-calculating the main diagonal of `memo`

and the diagonal above it should be trivial. The values on the main diagonal are always 1, as we’ve noticed above. The values on the diagonal above it are the numbers of steps required to print 2-letter strings, which are either 1 or 2, depending on whether the letters are equal or not, which we can easily figure out. So the matrix should look as follows:

`1 2 .........`

1 1 .......

1 1 .....

1 2 ...

.....

1

We could pre-calculate it using the following code during the matrix initialization:

`int N = array.length;`

memo = new int[N][];

for (int i = 0; i < N; i++) {

memo[i] = new int[N];

memo[i][i] = 1;

if (i != N - 1) {

int next = i + 1;

memo[i][next] = array[i] == array[next] ? 1 : 2;

}

}

# The complete solution

Here’s the complete solution with all the optimizations above:

`public class StrangePrinter {`

private int[][] memo;

private char[] array;

public int strangePrinter(String s) {

if (s.isEmpty()) {

return 0;

}

array = squash(s);

int N = array.length;

memo = new int[N][];

for (int i = 0; i < N; i++) {

memo[i] = new int[N];

memo[i][i] = 1;

if (i != N - 1) {

int next = i + 1;

memo[i][next] = array[i] == array[next] ? 1 : 2;

}

}

return sp(0, array.length - 1);

}

public int sp(int i, int j) {

if (i > j) {

return 0;

}

if (memo[i][j] == 0) {

int nextIdx = i + 1;

int letter = array[i];

int answer = 1 + sp(nextIdx, j);

for (int k = nextIdx; k <= j; k++) {

if (array[k] == letter) {

int betterAnswer = sp(i, k - 1) + sp(k + 1, j);

answer = Math.*min*(answer, betterAnswer);

}

}

memo[i][j] = answer;

}

return memo[i][j];

}

char[] squash(String s) {

char[] chars = s.toCharArray();

int last = 0;

int fullLength = chars.length;

for (int i = 1; i < fullLength; i++) {

if (chars[i] != chars[last]) {

chars[++last] = chars[i];

}

}

return Arrays.*copyOf*(chars, last + 1);

}

}