Strange Printer — Solution in Python, Java & C++
Strange Printer solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Strange Printer is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A strange printer can only do one thing per turn: print a sequence of one repeated character, overwriting whatever was already in the positions it covers.
Return the minimum number of turns needed to print s.
Example 1
Input: s = "codekairo"
Output: 8
Explanation: The repeated `o` lets one turn cover both ends of the word.
Example 2
Input: s = "aaabbb"
Output: 2
Explanation: Print `aaa`, then `bbb`.
Example 3
Input: s = "aba"
Output: 2
Explanation: Print `aaa`, then overwrite the middle with `b`.
Constraints
1 <= s.length <= 100s consists of lowercase English letters.
Hints for Strange Printer
Hint 1
Think of the last character. Printing it can be merged with an earlier turn that printed the same character.
Hint 2
dp[i][j]= the minimum turns fors[i..j].Hint 3
Start from
dp[i][j-1] + 1, then try merging with each earlier positionkwheres[k] == s[j].
How to solve Strange Printer
Interval DP. dp[i][j] is the minimum turns for s[i..j]. The baseline is printing s[j] in its own turn: dp[i][j-1] + 1. But whenever some k < j has s[k] == s[j], that earlier turn can be stretched to cover position j for free, splitting the interval into s[i..k] and s[k+1..j-1].
Approach
- Set
dp[i][i] = 1. - For increasing lengths, start with
dp[i][j] = dp[i][j-1] + 1. - For each
kfromitoj-1withs[k] == s[j], takedp[i][k] + dp[k+1][j-1]. - Return
dp[0][n-1].
Why it works
The merge is the whole problem. Overwriting means a single turn's stroke can extend past characters that are printed over later, so two equal characters far apart may cost one turn between them rather than two. Splitting at k and excluding j from the right interval is what encodes "the stroke that printed s[k] also printed s[j]" — an off-by-one there quietly double-counts the merged turn.
Complexity
- Time —
O(n³) - Space —
O(n²)
Pitfalls
- The right sub-interval is
s[k+1..j-1], nots[k+1..j]. - That sub-interval can be empty when
k = j-1; treat it as 0 turns. - Collapsing runs of equal characters first is a valid and useful preprocessing step, but the DP must still handle them.
Reference solution
Python
def strangePrinter(s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = dp[i][j - 1] + 1
for k in range(i, j):
if s[k] == s[j]:
inner = dp[k + 1][j - 1] if k + 1 <= j - 1 else 0
dp[i][j] = min(dp[i][j], dp[i][k] + inner)
return dp[0][n - 1]Java
public static int strangePrinter(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = dp[i][j - 1] + 1;
for (int k = i; k < j; k++) {
if (s.charAt(k) == s.charAt(j)) {
int inner = k + 1 <= j - 1 ? dp[k + 1][j - 1] : 0;
dp[i][j] = Math.min(dp[i][j], dp[i][k] + inner);
}
}
}
}
return dp[0][n - 1];
}C++
int strangePrinter(string s) {
int n = (int) s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
dp[i][j] = dp[i][j - 1] + 1;
for (int k = i; k < j; k++) {
if (s[k] == s[j]) {
int inner = k + 1 <= j - 1 ? dp[k + 1][j - 1] : 0;
dp[i][j] = min(dp[i][j], dp[i][k] + inner);
}
}
}
}
return dp[0][n - 1];
}JavaScript
var strangePrinter = function(s) {
var n = s.length, i, j;
var dp = [];
for (i = 0; i < n; i++) {
var row = [];
for (j = 0; j < n; j++) row.push(0);
dp.push(row);
}
for (i = 0; i < n; i++) dp[i][i] = 1;
for (var len = 2; len <= n; len++) {
for (i = 0; i + len - 1 < n; i++) {
j = i + len - 1;
dp[i][j] = dp[i][j - 1] + 1;
for (var k = i; k < j; k++) {
if (s.charAt(k) === s.charAt(j)) {
var inner = k + 1 <= j - 1 ? dp[k + 1][j - 1] : 0;
if (dp[i][k] + inner < dp[i][j]) dp[i][j] = dp[i][k] + inner;
}
}
}
}
return dp[0][n - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming