Strange Printer
Asked at Salesforce
Problem
A strange printer can only print a sequence of the same character in each turn. In each turn, the printer can print characters over any existing characters on the paper. Given a string s, return the minimum number of turns the printer needs to print it.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | Hard | View all Salesforce questions → |
How to Think About It
Brute force: Try every possible way to split the string and count turns for each character, exploring all recursive decompositions.
Improved: Use recursion with memoization. For each substring s[i..j], try every possible split point k and minimize turns.
Better: Define dp[i][j] as the minimum turns to print s[i..j]. If s[i] == s[j], we can extend a turn from dp[i+1][j] or dp[i][j-1].
Refined: dp[i][j] = min over all k in [i, j) of dp[i][k] + dp[k+1][j]. Additionally, if s[i] == s[j], dp[i][j] = min(dp[i][j], dp[i+1][j]).
Optimal: Bottom-up DP on intervals. dp[i][j] = dp[i+1][j] if s[i] == s[i+1] since the first character can be printed together. Otherwise iterate splits. O(n^3) time, O(n^2) space.
Optimal Approach
This is an interval DP problem. Define dp[i][j] as the minimum number of turns to print s[i..j]. For a single character, dp[i][i] = 1. For a substring of length > 1, try every split point k between i and j-1: dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]). Additionally, if s[i] == s[j], the character at position j can be printed in the same turn as position i, so dp[i][j] = min(dp[i][j], dp[i+1][j]). The reason this works is that when s[i] == s[j], we can print the entire character during the same pass that covers position i, so we only need to handle the middle. Fill the DP table from smaller substrings to larger ones. Time: O(n^3), Space: O(n^2).
Solution Code
def strangePrinter(s):
n = len(s)
if n == 0:
return 0
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 + 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 + 1][k - 1] + dp[k][j])
return dp[0][n - 1]Frequently Asked Questions
What is the Strange Printer problem?
A strange printer can only print a sequence of the same character in each turn. In each turn, the printer can print characters over any existing characters on the paper. Given a string s, return the minimum number of turns the printer needs to print it.
How do you solve Strange Printer?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Strange Printer?
Strange Printer is asked at Salesforce. It is a hard difficulty problem.