Strange Printer - Solution & Explanation
Problem Statement
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.
Example 1:
Input: s = "aaabbb" Output: 2 Explanation: Print "aaa" first and then print "bbb".
Example 2:
Input: s = "aba" Output: 2 Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.
Constraints:
1 <= s.length <= 100sconsists of lowercase English letters.
Approach Overview
Problem Overview: You are given a string s. A special printer can print a sequence of identical characters in one turn and can overwrite existing characters. The goal is to compute the minimum number of turns required to print the entire string.
Approach 1: Greedy Segment Coverage (O(n^2) time, O(n) space)
This approach relies on the observation that consecutive duplicate characters do not change the number of turns required. You first compress the string by removing adjacent duplicates, which reduces unnecessary states. Then iterate through the compressed string and try to extend segments where the same character appears again later. By greedily covering these matching characters in a single printing turn, you reduce the total number of operations. This strategy works well when the string contains repeating patterns because a single print can overwrite previously printed characters and merge segments.
Approach 2: Dynamic Programming with Memoization (O(n^3) time, O(n^2) space)
The optimal solution uses interval dynamic programming. Define dp[i][j] as the minimum number of turns needed to print the substring from index i to j. Start with the idea that printing s[i] alone requires one turn plus the cost of printing the remaining substring dp[i+1][j]. Then iterate through indices k where s[k] == s[i]. If the printer prints both characters in the same turn, the interval can be split into dp[i][k-1] + dp[k+1][j], reducing redundant prints. Memoization ensures each substring state is computed once, turning the recursive exploration into a manageable O(n^3) process. The DP table has O(n^2) states and each state may scan the interval to merge matching characters.
This problem is a classic example of interval DP similar to matrix chain multiplication or palindrome partitioning. The key trick is recognizing that matching characters allow you to merge print operations across different positions.
Recommended for interviews: Interviewers expect the Dynamic Programming with Memoization solution. It demonstrates strong understanding of interval DP and state transitions. Discussing the greedy idea shows intuition about segment merging, but implementing the DP recurrence correctly proves you can reason about overlapping subproblems. Review related patterns under dynamic programming and string interval problems in string algorithms.
Approach 1: Dynamic Programming with Memoization
This approach involves using dynamic programming with memoization to find the minimum number of turns needed to print the string. The idea is to define a recursive function that prints a substring from index i to index j, using memoization to avoid unnecessary repeated calculations.
This C solution uses a recursive function minTurns with memoization to calculate the minimum prints for a given substring. The main idea is to cover a segment and recursively calculate for the remaining parts. The dp table stores previously calculated results to optimize the performance.
Complexity
Time Complexity: O(n^3), Space Complexity: O(n^2)
Approach 2: Greedy Segment Coverage
This approach uses a greedy strategy to minimize the number of character segments that need to be printed. Instead of forming a full dp matrix, it strategizes the printing operations based on visible segments of similar characters, exploiting shared coverage.
This optimized greedy Python solution leverages a streamlined version of the string by compressing repeated characters. It utilizes memoization within a divided recursive structure. Segments are collapsed as the helper ranges over valid substrings, aiming for spaced repetition minimization.
Code
Python
Complexity
Time Complexity: O(n^3), Space Complexity: O(n^2). This primarily stems from recursive splitting subproblems by string breakdown.
Approach 3: Dynamic Programming
We define f[i][j] as the minimum operations to print s[i..j], with the initial value f[i][j]=infty, and the answer is f[0][n-1], where n is the length of string s.
Consider f[i][j], if s[i] = s[j], we can print s[j] when print s[i], so we can ignore s[j] and continue to print s[i+1..j-1]. If s[i] neq s[j], we need to print the substring separately, i.e. s[i..k] and s[k+1..j], where k \in [i,j). So we can have the following transition equation:
$
f[i][j]=
\begin{cases}
1, & if i=j \
f[i][j-1], & if s[i]=s[j] \
min_{i leq k < j} {f[i][k]+f[k+1][j]}, & otherwise
\end{cases}
We can enumerate i from large to small and j from small to large, so that we can ensure that f[i][j-1], f[i][k] and f[k+1][j] have been calculated when we calculate f[i][j].
The time complexity is O(n^3) and the space complexity is O(n^2). Where n is the length of string s$.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Memoization | Time Complexity: O(n^3), Space Complexity: O(n^2) |
| Greedy Segment Coverage | Time Complexity: O(n^3), Space Complexity: O(n^2). This primarily stems from recursive splitting subproblems by string breakdown. |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Segment Coverage | O(n^2) | O(n) | Quick heuristic approach when strings contain many repeating segments |
| Dynamic Programming with Memoization | O(n^3) | O(n^2) | General optimal solution expected in interviews and coding platforms |
Video Solution
Strange Printer | INTUITIVE | Recursion | Memoization | NetEase | Leetcode-664 • codestorywithMIK • 20,498 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Strange Printer easy or hard?
Strange Printer Python/Java solution
How to solve Strange Printer in O(n)?
What is the best approach for Strange Printer?
Is Strange Printer asked at Google/Amazon/Meta?
What data structure is used in Strange Printer?
What is the time complexity of Strange Printer?
Ready to solve this problem?
Practice Strange Printer with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor