Strange Printer solution and explanation
Google
9 more videos on this problem
Strange Printer | INTUITIVE | Recursion | Memoization | NetEase | Leetcode-664codestorywithMIK · 31:00 · 20K views
Leetcode 664. Strange Printer II Matrix Chain Multiplication II DP || Complete IntuitionAryan Mittal · 13:50 · 16K views
LeetCode 664. Strange PrinterHappy Coding · 21:31 · 11K views
Taming the LeetCode 664. Strange Printer A Dynamic Programming Adventure in Python 🖨️🚀vanAmsen · 12:43 · 2K views
664. Strange Printer (Leetcode Hard)Programming Live with Larry · 1:00:47 · 1K views
Daily Leetcode #1216: Jul 30, 2023 - 664. Strange PrinterProgramming Live with Larry · 30:55 · 999 views
Strange Printer - LeetCode 664 - PythonAlpha-Code · 13:07 · 822 views
LeetCode 664 - Strange Printer - JavaAlpha-Code · 15:28 · 822 views
Leetcode 664. Strange PrinterAlgorithms for Big Bucks · 7:12 · 567 views
664 Strange Printer LeetcodeGeekNerd · 29:50 · 421 views
The problem
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.
class Solution:
def strangePrinter(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for length in range(1, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = dp[i + 1][j] + 1
for k in range(i + 1, j + 1):
if s[k] == s[i]:
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]
sol = Solution()
print(sol.strangePrinter("aba"))class Solution {
public int strangePrinter(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int len = 1; len <= n; ++len) {
for (int i = 0; i + len <= n; ++i) {
int j = i + len - 1;
dp[i][j] = (i == j) ? 1 : dp[i + 1][j] + 1;
for (int k = i + 1; k <= j; ++k) {
if (s.charAt(k) == s.charAt(i)) {
dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + (k + 1 <= j ? dp[k + 1][j] : 0));
}
}
}
}
return dp[0][n - 1];
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "aba";
System.out.println(solution.strangePrinter(s));
}
}#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
static int strangePrinter(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 1; len <= n; ++len) {
for (int i = 0; i + len <= n; ++i) {
int j = i + len - 1;
dp[i][j] = (i == j) ? 1 : dp[i + 1][j] + 1;
for (int k = i + 1; k <= j; ++k) {
if (s[k] == s[i]) {
dp[i][j] = min(dp[i][j], dp[i][k - 1] + (k + 1 <= j ? dp[k + 1][j] : 0));
}
}
}
}
return dp[0][n - 1];
}
};
int main() {
Solution solution;
string s = "aba";
cout << solution.strangePrinter(s) << endl;
return 0;
}function strangePrinter(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));
for (let len = 1; len <= n; len++) {
for (let i = 0; i + len <= n; i++) {
let j = i + len - 1;
dp[i][j] = (i === j) ? 1 : dp[i + 1][j] + 1;
for (let k = i + 1; k <= j; k++) {
if (s[k] === s[i]) {
dp[i][j] = Math.min(dp[i][j], dp[i][k - 1] + (k + 1 <= j ? dp[k + 1][j] : 0));
}
}
}
}
return dp[0][n - 1];
}
console.log(strangePrinter('aba'));#include <stdio.h>
#include <string.h>
#define MAX 100
int dp[MAX][MAX];
int minTurns(char *s, int i, int j) {
if (i > j) return 0;
if (dp[i][j] != -1) return dp[i][j];
dp[i][j] = minTurns(s, i + 1, j) + 1;
for (int k = i + 1; k <= j; ++k) {
if (s[k] == s[i]) {
dp[i][j] = fmin(dp[i][j], minTurns(s, i, k - 1) + minTurns(s, k + 1, j));
}
}
return dp[i][j];
}
int strangePrinter(char *s) {
int n = strlen(s);
memset(dp, -1, sizeof dp);
return minTurns(s, 0, n - 1);
}
int main() {
char s[] = "aba";
printf("%d\n", strangePrinter(s));
return 0;
}using System;
public class Solution {
public int StrangePrinter(string s) {
int n = s.Length;
int[,] dp = new int[n, n];
for (int len = 1; len <= n; ++len) {
for (int i = 0; i + len <= n; ++i) {
int j = i + len - 1;
dp[i, j] = (i == j) ? 1 : dp[i + 1, j] + 1;
for (int k = i + 1; k <= j; ++k) {
if (s[k] == s[i]) {
dp[i, j] = Math.Min(dp[i, j], dp[i, k - 1] + (k + 1 <= j ? dp[k + 1, j] : 0));
}
}
}
}
return dp[0, n - 1];
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.StrangePrinter("aba"));
}
}The Python solution also uses dynamic programming to fill a 2D dp array. The array helps manage overlapping problems, focusing on minimizing printing operations for increasing segment lengths, checked using nested loops across segments characterized by identical characters.
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.
class Solution:
def strangePrinter(self, s: str) -> int:
if not s:
return 0
compressed = []
for ch in s:
if not compressed or compressed[-1] != ch:
compressed.append(ch)
def helper(l, r):
if l > r:
return 0
ret = helper(l + 1, r) + 1
for i in range(l + 1, r + 1):
if compressed[i] == compressed[l]:
ret = min(ret, helper(l, i - 1) + helper(i + 1, r))
return ret
return helper(0, len(compressed) - 1)
sol = Solution()
print(sol.strangePrinter("aba"))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.
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$.
function strangePrinter(s: string): number {
const n = s.length;
const f: number[][] = new Array(n).fill(0).map(() => new Array(n).fill(1 << 30));
for (let i = n - 1; i >= 0; --i) {
f[i][i] = 1;
for (let j = i + 1; j < n; ++j) {
if (s[i] === s[j]) {
f[i][j] = f[i][j - 1];
} else {
for (let k = i; k < j; ++k) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j]);
}
}
}
}
return f[0][n - 1];
}func strangePrinter(s string) int {
n := len(s)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
for j := range f[i] {
f[i][j] = 1 << 30
}
}
for i := n - 1; i >= 0; i-- {
f[i][i] = 1
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
f[i][j] = f[i][j-1]
} else {
for k := i; k < j; k++ {
f[i][j] = min(f[i][j], f[i][k]+f[k+1][j])
}
}
}
}
return f[0][n-1]
}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 | – |
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 |
Frequently asked questions
Is Strange Printer easy or hard?
Strange Printer is classified as a Hard problem on LeetCode. The difficulty comes from identifying the interval DP formulation and the optimization where matching characters allow merging of print operations.
Strange Printer Python/Java solution
Python and Java implementations typically use top-down recursion with memoization or bottom-up DP tables. Both versions store results for substring ranges and apply the merge rule when identical characters appear later in the interval.
How to solve Strange Printer in O(n)?
An O(n) exact algorithm is not known for the general case. The best widely accepted solution uses interval dynamic programming with O(n^3) time. Some implementations reduce constant factors by compressing consecutive duplicate characters before running DP.
What is the best approach for Strange Printer?
The best approach uses interval Dynamic Programming. Define dp[i][j] as the minimum turns required to print substring s[i..j]. If characters match later in the substring, their print operations can be merged to reduce turns. This solution runs in O(n^3) time with O(n^2) space and is the standard accepted approach.
Is Strange Printer asked at Google/Amazon/Meta?
Strange Printer appears in advanced algorithm interview prep sets and has been reported in interviews at companies that emphasize dynamic programming such as Google and Meta. It tests interval DP reasoning and optimization of overlapping subproblems.
What data structure is used in Strange Printer?
The core data structure is a 2D dynamic programming table where dp[i][j] stores the minimum turns needed for substring s[i..j]. The algorithm also relies on string traversal and memoization to avoid recomputing subproblems.
What is the time complexity of Strange Printer?
The optimal dynamic programming solution runs in O(n^3) time and O(n^2) space. There are O(n^2) substring states and each state may iterate through the interval to find matching characters that allow merging print operations.