Strange Printer

10 Prerequisite LeetCode Problems

“664. Strange Printer” is a dynamic programming problem with considerations about string manipulation. Here are 10 problems to prepare:

  1. “516. Longest Palindromic Subsequence”: This problem helps understand basic dynamic programming techniques applied on a string.

  2. “72. Edit Distance”: This problem introduces the concept of DP with two string pointers.

  3. “1143. Longest Common Subsequence”: It teaches the implementation of classic dynamic programming for string analysis.

  4. “718. Maximum Length of Repeated Subarray”: Similar to the above, but it focuses on subarray.

  5. “647. Palindromic Substrings”: It combines dynamic programming with the concept of palindrome.

  6. “132. Palindrome Partitioning II”: It combines dynamic programming with the concept of palindrome and partitioning.

  7. “312. Burst Balloons”: This problem introduces the concept of interval DP which is also used in the Strange Printer problem.

  8. “375. Guess Number Higher or Lower II”: Another problem to practice interval DP.

  9. “300. Longest Increasing Subsequence”: It teaches how to use dynamic programming to track subproblems in a sequence.

  10. “139. Word Break”: A different style of dynamic programming problem that breaks down a string into subproblems.

These cover dynamic programming and string manipulation, both of which are crucial for solving the “Strange Printer” problem.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

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

The Python function strangePrinter is designed to find the minimum number of turns the printer will take to print a string s. The printer can print a sequence of the same character in one turn, but it cannot print substrings.

Here’s how the function works:

  1. It starts by determining the length n of the string s and initializing a two-dimensional list dp of size n x n with all elements set to 0. This dp list will be used for dynamic programming to store the minimum number of turns required to print the substring s[i:j+1].

  2. It then iterates over the string from the end to the beginning (i.e., in reverse order). For each index i, it iterates over all indices from i to n.

  3. If i is equal to j (i.e., the substring has only one character), it sets dp[i][j] to 1, because it takes only one turn to print a single character. Otherwise, it sets dp[i][j] to dp[i+1][j] + 1, which assumes that the first character is printed separately and then the rest of the substring is printed.

  4. Then, it iterates over all indices k from i+1 to j+1. If s[i] is equal to s[k], it means that the substring s[i:k] can be printed in one turn. So, it updates dp[i][j] to be the minimum of its current value and the sum of dp[i][k-1] and dp[k+1][j] (the latter only if k+1 is within the bounds).

  5. Finally, it returns dp[0][n-1], which is the minimum number of turns required to print the entire string.

This function effectively uses dynamic programming to calculate the minimum number of turns for all substrings in a bottom-up manner, resulting in a time complexity of O(n^3), where n is the length of the string s. The space complexity is O(n^2), as it creates a two-dimensional list of size n x n.

Identifying Problem Isomorphism

“Strange Printer” can be mapped to “Remove Boxes”.

In both problems, we have a sequence (string or array) and we’re trying to minimize an operation (number of turns or maximize points). Both problems use dynamic programming with a 3D dp array. We partition our sequence into segments and solve for those recursively.

“Remove Boxes” is simpler as it involves maximization within contiguous segments of same elements while “Strange Printer” involves more complex manipulation due to printer’s ability to overwrite.

Another isomorphic problem is “Palindrome Removal”. In this problem, like the previous ones, we are given a sequence (array of integers) and our goal is to minimize operations (removing palindromic subsequence). The subproblem definitions are similar and the problem also uses dynamic programming.

“Palindrome Removal” is more complex because the operations can remove a sequence from anywhere in the array, not just at the ends, which introduces an extra layer of complexity in the recurrence relation.

So, the mapping from simpler to more complex is:

  • “Remove Boxes”
  • “Strange Printer”
  • “Palindrome Removal”.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

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

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

        return dp[0][n-1]

Problem Classification

This problem falls into the domain of “Dynamic Programming”. It requires knowledge of string manipulation and understanding of the state transition and optimization over time, typical in dynamic programming problems.

Problem Components:

  1. Input: The input is a string ’s’. This is the string that the printer needs to print.
  2. Output: The output is an integer. This represents the minimum number of turns the printer needs to print the input string.
  3. Constraints: 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.

Problem Classification:

  1. Optimization Problem: This problem is an optimization problem where you need to find a strategy for the printer that minimizes the number of turns it needs to print a string.
  2. Dynamic Programming: The problem can be solved using dynamic programming. A possible approach is to use a DP table where each cell dp[i][j] represents the minimum number of turns the printer needs to print the substring s[i…j]. The transition states are dependent on whether or not the characters at the start and end of the substring are the same, which allows the printer to print them in one turn.
  3. String Manipulation: The problem requires dealing with strings and substrings.

Given the constraints of the problem and the required output, it fits best in the dynamic programming category because of its characteristics of overlapping sub-problems (common in DP problems) and the need for optimization (finding the minimum number of turns). Furthermore, as it involves operation on a string input, it also involves string manipulation.

  1. String Manipulation: The problem deals with a string input and requires manipulation and analysis of the string’s characters.

  2. Optimization Problem: The problem asks to find the minimum number of turns required to print the string, which indicates it’s an optimization problem.

  3. Dynamic Programming: Although not explicitly mentioned in the problem statement, the concept of overlapping sub-problems and the need to find an optimal solution hint at dynamic programming as a possible approach.

  4. Subsequence/Substring Problem: The problem deals with substrings of the input string and finding an optimal solution over these substrings.

  5. Decision Making: The problem requires making the right decisions (e.g., when to print certain characters together) to arrive at the optimal solution.

Language Agnostic Coding Drills

  1. String Manipulation: The solution involves traversing and comparing characters within a string. Familiarize yourself with how to access elements in a string, check if two elements are equal, and how to iterate over a string from beginning to end, and in reverse.

  2. Dynamic Programming: The problem uses dynamic programming (DP) to store and reuse previously computed results, thus optimizing the solution. Understand how to initialize a DP table, set base cases, and formulate the state transition relation.

  3. Matrix Manipulation: The solution uses a 2D DP table, which is a form of matrix. You should know how to create a 2D matrix, access its elements, and iterate over it row-wise or column-wise.

  4. Looping Structures: The solution uses nested loops to fill the DP table. Understand how to write nested loops and the effect of their order on the computations.

  5. Conditional Statements: The solution involves making decisions based on certain conditions, such as whether two string characters are equal. You need to understand how to write if-else statements.

  6. Minimization/Maximization: The problem involves finding the minimum number of turns the printer needs, which is a minimization problem. Understand how to use comparison operations to keep track of minimum or maximum values encountered.

Problem-solving Approach:

  1. Begin by understanding that the problem is asking for the minimum number of turns a printer needs to print a given string.

  2. Notice that the printer can print consecutive same characters in one turn, and thus decide to use dynamic programming to find the minimum number of turns needed.

  3. Set up a 2D DP table, where dp[i][j] represents the minimum number of turns the printer needs to print the substring s[i:j].

  4. Start filling up the DP table by setting the base cases. A single character always needs one turn to print, so set dp[i][i] to 1 for all i.

  5. Now, use a nested loop structure to fill up the rest of the DP table. If s[i] is the same as s[j], then dp[i][j] should be the same as dp[i][j-1], as the printer can print s[i] and s[j] in one turn.

  6. Otherwise, find the minimum turns needed to print s[i:j] by dividing the substring into two parts at k, and summing the turns needed for each part. Do this for all possible k between i and j, and choose the minimum.

  7. Finally, dp[0][n-1] will contain the minimum number of turns needed to print the whole string. Return this value.

Targeted Drills in Python

Drill 1 - String Manipulation Exercise: Given a string, write a function to iterate over its characters.

1
2
3
4
5

def iterate_chars(s):
    for c in s:
        print(c)

iterate_chars("hello")

Drill 2 - Initializing 2D List Exercise: Given an integer ’n’, create a 2D list (matrix) of size ’n x n’ and initialize it with 0.

1
2
3
4
5

def init_2D_list(n):
    dp = [[0]*n for _ in range(n)]
    print(dp)

init_2D_list(5)

Drill 3 - Reverse Iteration Exercise: Write a function that prints the numbers from ’n-1’ to ‘0’ (inclusive) in descending order.

1
2
3
4
5

def reverse_iter(n):
    for i in range(n-1, -1, -1):
        print(i)

reverse_iter(5)

Drill 4 - Dynamic Programming Exercise: Create a 2D list ‘dp’ where ‘dp[i][j]’ stores the sum of ‘dp[i][k]’ and ‘dp[k+1][j]’.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def sum_dp(n):
    dp = [[0]*n for _ in range(n)]

    for i in range(n-1, -1, -1):
        for j in range(i+1, n):
            for k in range(i, j):
                dp[i][j] = dp[i][k] + dp[k+1][j]
    print(dp)

sum_dp(5)

Drill 5 - Conditional Checks and Updates Exercise: Write a function that checks if two characters in a string are the same and if so, update the corresponding ‘dp’ value.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def check_chars(s, n):
    dp = [[0]*n for _ in range(n)]

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

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

check_chars("hello", 5)

All these exercises provide the foundational elements of the final solution. They can be combined and modified to create the final solution that solves the problem.

Q&A

This might be a dumb question. But I can’t seem to understand the constraints of the question:

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 places, and will cover the original existing characters.

For example: For the string “abcabc”, the answer is 5 Why can’t we print “aaaa” covering ‘a’ to ‘a’, then “bbbb” covering ‘b’ to ‘b’ and then “cccc” covering ‘c’ to ‘c’. making it 3.

Trivially the answer will end up to be the # of unique chars in the string, which obviously is not the case!

Can someone please reword the question?

The printer has two rules:

  1. The printer can only print a sequence of the same character each time: This means that if the printer starts printing, it can only print the same character until it stops. For instance, it can print “aaaa” or “bbbb”, but it can’t print “abab” in one go.

  2. At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters: This rule is a bit trickier. It allows the printer to start and stop printing at any places in the string, and if it prints over already printed characters, the new characters replace the old ones.

Here is where the confusion seems to come in. When the printer prints a character, it “covers” any existing characters in that range. This is why the printer can’t just print all ‘a’s, then all ‘b’s, then all ‘c’s in your example.

Let’s take your example “abcabc”. If the printer first prints “aaaaaa” (replacing ‘a’ to ‘a’), then the string becomes “aaaaaa”. Now, if the printer tries to print “bbbb” covering ‘b’ to ‘b’, there are no ‘b’s left in the string, so the printer actually can’t do this in one turn. Instead, it would have to print one ‘b’ at a time, at two different places, which would take two turns, not one.

So, the strategy of printing all of each character at once doesn’t work, because as soon as you print the first character, you cover all the positions where the next character would go.

That’s why we need a more sophisticated strategy to minimize the number of turns. For example, in “abcabc”, a good strategy might be to print “aaaaaa”, then print “bb” in the middle, then “cc” in the middle of that. This would take only three turns.