HardStringDynamic ProgrammingUpdated Sep 2026

664. Strange Printer

Asked at Salesforce

Difficulty

Hard

Time

O(n^3)

Space

O(n^2)

Pattern

String

Companies

1

Problem

A strange printer prints on one line of paper. In a single turn it can only print one repeated character, but it may choose any start and end position, and it paints over whatever was already there.

You are given a string s. Return the minimum number of turns the printer needs so the paper finally shows exactly s.

Think of it as painting: each turn you pick a letter and a range, and that range becomes that letter. Later turns can overwrite earlier ones. The trick is that one turn can serve several far-apart positions of the same letter, because the letters printed in between can be added later on top.

One turn paints one letter over a range

aba012Turn 1: print 'a' from position 0 to position 2aba012Turn 2: print 'b' at position 1, covering the old 'a'
Turn 1 paints "aaa" across the whole string, turn 2 paints "b" only in the middle, giving "aba" in 2 turns.

Constraints

  • ●1 <= s.length <= 100
  • ●s consists of lowercase English letters only

Examples

Example 1
Inputs = "aaabbb"
Output2
WhyPrint "aaa" over positions 0-2, then print "bbb" over positions 3-5. Two turns, and nothing gets overwritten.
Example 2
Inputs = "aba"
Output2
WhyPrint "aaa" over the whole string in turn 1, then print "b" only at position 1 in turn 2. The second turn covers the middle 'a', so 2 turns are enough. One turn is impossible because a single turn prints only one letter.

Asked At

1 companies
CompanyDifficulty
SalesforceHardView all Salesforce questions →

How to Think About It

1

Brute force: Try every possible way to split the string and count turns for each character, exploring all recursive decompositions.

2

Improved: Use recursion with memoization. For each substring s[i..j], try every possible split point k and minimize turns.

3

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].

4

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]).

5

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).

Interval DP: reuse the ends

dp012012122121s = "aba": dp[0][2] = 2, because s[0] == s[2] lets the last 'a' jointhe first turndp[i][i] = 1dp[i][j] = dp[i+1][j] + 1if s[k] == s[i]: dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j
dp[i][j] is the fewest turns for s[i..j]. When both ends hold the same letter, the right end can ride along with the left end's turn.
ComplexityTime O(n^3)Space O(n^2)There are O(n^2) intervals, and each one scans up to O(n) split points; the table of intervals costs O(n^2) memory.

Solution Code

O(n^3) time
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]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

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 runs in O(n^3) time and O(n^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Strange Printer?

Strange Printer is asked at Salesforce. It is a hard difficulty problem.