Strange Printer

Problem Statement

Suppose you have a printer that can print a sequence of the same character each time. Each "turn", you can print any character starting and ending from any position. For example, if you wanted to create the string aabba, the sequence would be:

1. Print "aaaaa"
2. Overlap with "aaabba"

Costing two total turns. Thus, given an input string s, compute the minimum number of turns it takes to print the string.

Solution

The first thing I always do is just think through a naive algorithm and ask myself what decisions are made at each step. Given any input string, you can try to layout the character that occurs the most. Then second most, and so on. However, this comes with problems when you see strings like abab, because what happens when abbb is there? Also, a hint in the problem is that we want to find the minimum number of turns. Finally, problems where previous decisions are heavily interleaved with future ones (in non-obvious ways) is a very strong signal for DP.

So our next step is to identify the states of the problem. What are we keeping track of here. There are essentially just two options for this:

1. The number of turns it takes to get to the i'th position in the string: dp[i]
2. The number of turns it takes to create s[i...j]: dp[i][j].

After some thinking, the first approach is not viable as it may disregard certain patterns in the string, resulting in an unnecessary step or harder calculation. So now, we have our answer Interval DP. Our base case is then simple: dp[i][i] = 1, since for every letter it obviously takes 1 turn to output that letter.

dp = [[0] * n for _ in range(n)
# Base Case
for i in range(n):
	dp[i][i] = 1

Now we have our main block of code which should orchestrate the connection between intervals of various sizes. Intuitively, we want to start off with smaller intervals and expand to larger ones. Then, for our given interval size, we want to move over the input string in a sliding-window style pass:

for length in range(2, n + 1):
	for i in range(n - length + 1):

	# Worst case scenario, you just add 1
	j = i + length - 1
	dp[i][j] = dp[i][j - 1] + 1

You'll notice that for every inner loop iteration, you start off by assuming the worse: an extra print for just one character. At this point we have isolated a length size interval from i to j and we have our worst case answer on the answer for this substring. How can we possibly find a better answer? With the tools we have right now, there isn't really a way do to anything else. Since we want to decrease dp[i][j] further, we should see if we can break it up in a different way: with a third loop.

The idea of the third loop is simple: iterate through pivot indices within the current interval and see if two substrings can be combined in fewer turns than what we currently have.

for k in range(i, j):
	if s[k] == s[j]:
		dp[i][j] = min(
			dp[i][j],
			dp[i][k] + dp[k + 1][j - 1]
		)

Above, for every pivot index we ask, does the number of turns it take to make the first section of the string and the last section of the string decrease the total number of turns? Notice that the program looks specifically at [k+1, j-1] since you know that s[k] == s[j], there is no operation needed to complete the validity of the string as the sub-interval is completely contained. This is a very clever solution and one that is not immediately obvious, but with strong perception of the choice and tools you have available at every step, the thought process makes sense. At the end, we return the number of steps it takes for the largest intervalThe length of the string:

def strangePrinter(self, s: str) -> int:
	n = len(s)
	if n == 0:
		return 0
		
	dp = [[0] * n for _ in range(n)]

  

	# Base Case
	for i in range(n):
		dp[i][i] = 1
		
	for length in range(2, n + 1):
		for i in range(n - length + 1):
			# Worst case scenario, you just add 1
			j = i + length - 1

			dp[i][j] = dp[i][j - 1] + 1
			
			for k in range(i, j):
				if s[k] == s[j]:
					dp[i][j] = min(
						dp[i][j],
						dp[i][k] + dp[k + 1][j - 1]
					)

return dp[0][n - 1]