Leetcode Daily Question 21/08/2024 - 664. Strange Printer

Problem Description:

There is a strange printer with the following two special properties: The printer can only print a sequence of the same character each time. At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters. Given a string s, return the minimum number of turns the printer needed to print it.

class Solution:
  def strangePrinter(self, s: str) -> int:
    n = len(s)
    if n == 0:
      return 0 
    dup_removed = [s[0]]
    for i in range(1, n):
      if s[i] != s[i-1]:
        dup_removed.append(s[i])
    
    n = len(dup_removed)
    last_seen_index = {}
    next_occurrence_index = [n] * n
    
    for i in range(n-1,-1,-1):
      if dup_removed[i] in last_seen_index:
        next_occurence_index[i] = last_seen_index[dup_removed[i]]
      last_seen_index[dup_removed[i]] = i
      
    dp = [[0] * n for _ in range(n+1)]
    
    for i in range(n):
      dp[i][i] = 1
      
    for i in range(n-2,-1,-1):
      for j in range(i + 1, n):
        dp[i][j] = 1 + dp[i+1][j]
        k = next_occurence_index[i]
        while k <= j:
          dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j])
          k = next_occurrence_index[k]
    
    return dp[0][n-1]

Explanation:

We can solve this problem by dp. To start, we remove all consecutively duplicated letters from s. We can do this because prince "a" and printing "aaa" takes the same amount of turns.

def strangePrinter(s):
  n = len(s)
  dup_removed = [s[0]]
  for i in range(1,n):
    if s[i] != s[i-1]:
      dup_removed.append(s[i])

Then we track the last seen index and the next occurrence index of each letter, traversing in reverse. This helps to speed up the dp table filling process.

n = len(dup_removed) # this is our new length 
last_seen_index = {}
next_occurrence_index = [n] * n
for i in range(n-1,-1,-1):
  if dup_removed[i] in last_seen_index:
    next_occurence_index[i] = last_seen_index[dup_removed[i]]
  last_seen_index[dup_removed[i]] = i

Now to define the dp table, we can define dp[i][j] as the number of turns required to print the substring dup_removed[i:j+1].

To fill the table, we first deal with the case where i == j. This is a single letter and will take 1 turn to print.

dp = [[0] * n for _ in range(n+1)]

for i in range(n):
  dp[i][i] = 1

To fill the rest of the dp table, we decide which of the following is optimal:

- Printing the first character separately and solving for the remaining substring.
- Combining the printing of the first character with its next occurrence in the substring.

for i in range(n-2,-1,-1):
  for j in range(i+1,n):
    dp[i][j] = 1 + dp[i+1][j] # print the first letter and solve for the rest
    k = next_occurrence_index[i]
    while k <= j:
      dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j]) # see if printing with the next occurrence is better
      k = next_occurence_index[k] # update the next_occurrence index
return dp[0][n-1]

This solution has time complexity O(n^2) and space complexity of O(n^2).

The full solution can be found near the top of the page.