Strange Printer — Interval DP with Merge-on-Match

Problem Statement#

There is a strange printer with two special properties:

1. The printer can only print a sequence of the same character each time.
2. 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 needs to print s.

Example: s = "aaabbb" returns 2. Print "aaa" first, then "bbb".

Example: s = "aba" returns 2. Print "aaa" first, then overwrite the middle position with "b".

Example: s = "tbejtbej" returns 6. Repeated patterns require careful planning.

Constraints: 1 is less than or equal to s.length is less than or equal to 100. The bound is set so that O(n^3) interval DP fits comfortably.

Why This Problem Matters#

Strange Printer is one of the most-loved interval DP problems at Google, Amazon, Microsoft, and quant trading shops. It belongs to the same family as Matrix Chain Multiplication, Burst Balloons, and Palindrome Partitioning II — problems where the DP is naturally indexed on intervals [i, j] and the transition tries every "split point" or every "last operation."

What makes Strange Printer special is the merge-on-match optimization: when the endpoints of the interval are equal, the answer for the larger interval reuses the answer for a smaller one almost for free. Recognizing that lets you compress the DP and explain the recurrence elegantly.

If you can solve Strange Printer cleanly, you have demonstrated mastery over interval DP — a notoriously tricky pattern that catches many candidates off guard.

The Core Insight (Recurrence)#

Define dp[i][j] as the minimum number of printer turns to produce the substring s[i..j] (both indices inclusive).

Base: dp[i][i] = 1 (a single character requires one turn).

Recurrence: think about how the last turn that paints position j interacts with earlier turns. There are two cases.

Case 1: the turn that prints s[j] paints only position j. Then dp[i][j] = dp[i][j-1] + 1.

Case 2: the turn that prints s[j] extends from some earlier position k where s[k] == s[j]. The same continuous print (with possible overwrites in between) covers both. We split: dp[i][j] = dp[i][k] + dp[k+1][j-1] for all k in [i, j-1] with s[k] == s[j]. The dp[k+1][j-1] term assumes k+1 > j-1 reduces to 0.

Take the minimum over all candidates.

The merge-on-match insight is what makes this work: when s[k] == s[j], the last character "rides along" with an earlier print, saving a turn.

Equivalent simpler form: first preprocess s by collapsing consecutive duplicates (so "aaabbb" becomes "ab"). The recurrence stays the same but operates on the compressed string, sometimes giving a cleaner trace.

Building the DP Solution (Recursion to Memo to Tabulation)#

Top-down: solve(i, j) returns the answer for s[i..j]. Try Case 1 directly, then iterate k from i to j-1 and apply Case 2 wherever s[k] == s[j]. Memoize on (i, j) for O(n^2) states each computed in O(n), giving O(n^3) total.

Tabulation: allocate dp[n][n]. Initialize the diagonal to 1. Fill by interval length from 2 up to n. For each (i, j), start with dp[i][j] = dp[i][j-1] + 1 (Case 1), then loop k and minimize via Case 2.

This length-first ordering is the same pattern used in Longest Palindromic Subsequence, Burst Balloons, and Matrix Chain Multiplication — internalize the template.

Visual Dry Run (DP Table Trace)#

Trace s = "aba" (length 3).

Initialize the diagonal: dp[0][0] = dp[1][1] = dp[2][2] = 1.

Length 2:

• (0, 1): Case 1 gives dp[0][0] + 1 = 2. Case 2: s[0]=a, s[1]=b no match. So dp[0][1] = 2.
• (1, 2): Case 1 gives dp[1][1] + 1 = 2. Case 2: s[1]=b, s[2]=a no match. So dp[1][2] = 2.

Length 3:

• (0, 2): Case 1 gives dp[0][1] + 1 = 3. Case 2: try k = 0. s[0]=a, s[2]=a match. Value = dp[0][0] + dp[1][1] = 1 + 1 = 2. (When the inner range k+1..j-1 is non-empty.) Try k = 1. s[1]=b, s[2]=a no match. Final: min(3, 2) = 2.

Answer: dp[0][2] = 2. Matches expected. The two turns are: print "aaa" (one turn), then overwrite position 1 with "b" (one turn).

Optimized Solution — Space-Optimized Python and JavaScript#

Python#

class Solution:
    def strangePrinter(self, s: str) -> int:
        # Collapse consecutive duplicates for a cleaner DP.
        compact = []
        for ch in s:
            if not compact or compact[-1] != ch:
                compact.append(ch)
        s = ''.join(compact)
        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]

JavaScript#

var strangePrinter = function (s) {
  // Collapse consecutive duplicates.
  let compact = '';
  for (const ch of s) {
    if (compact.length === 0 || compact[compact.length - 1] !== ch) {
      compact += ch;
    }
  }
  s = compact;
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = 0; i < n; i += 1) dp[i][i] = 1;
  for (let length = 2; length <= n; length += 1) {
    for (let i = 0; i + length - 1 < n; i += 1) {
      const j = i + length - 1;
      dp[i][j] = dp[i][j - 1] + 1;
      for (let k = i; k < j; k += 1) {
        if (s[k] === s[j]) {
          const 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];
};

Complexity Analysis#

• Time: O(n^3). There are O(n^2) intervals, and each interval iterates a split point in O(n).
• Space: O(n^2) for the DP table.
• The collapse-consecutive-duplicates preprocessing is O(n) one-time and often shrinks n significantly on inputs like "aaaaaaaa".
• Memoization has the same asymptotics with extra recursion stack — usually O(n) deep.

Common Mistakes#

• Filling the table row by row. Interval DP requires fill-by-length so that smaller intervals are ready when needed.
• Forgetting to initialize dp[i][i] = 1. A single character takes one turn; missing it propagates wrong values.
• Using dp[k+1][j-1] without the k + 1 <= j - 1 guard. When the inner interval is empty (e.g., k + 1 > j - 1), treat the contribution as 0.
• Skipping the duplicate-collapse preprocessing. Inputs with long repeated runs balloon the DP unnecessarily.
• Confusing with Burst Balloons. Both are interval DP, but Burst Balloons indexes on the last balloon burst, not the last printed character.

Interview Tips#

• Open with: "This is interval DP. I will index dp[i][j] on the substring s[i..j] and reason about what the last printer turn covers." That earns immediate credit.
• Walk through the merge-on-match insight using "aba" or "aab" on the whiteboard. Show how a matching endpoint saves a turn.
• Discuss the duplicate-collapse preprocessing as a constant-factor speedup. Senior interviewers love that detail.
• For the O(n^3) loop ordering, explain length-first iteration and why row-major fails.

Follow-up Questions#

• Reconstruct the actual sequence of turns. Store the chosen split point k in a parallel table.
• Generalize to a printer that can also erase (replace runs with spaces). The recurrence gains another transition.
• Strange Printer II (LeetCode 1591) — colors with spatial bounds. Different DP, different technique (DAG topo sort).
• Print a 2D image with the same merge-on-match idea. Open research-flavored extension.

Key Takeaways#

• Strange Printer is the canonical interval DP with merge-on-match: when interval endpoints share a character, an earlier print extends to cover the later one.
• The recurrence has two branches: print position j alone (Case 1) or fold it into an earlier matching print (Case 2 over all split points k).
• Time complexity is O(n^3); the loop order must be length-first so smaller intervals are computed before larger ones.
• Preprocessing by collapsing consecutive duplicates shrinks n and is a standard interval-DP hygiene step.
• The pattern shares its skeleton with Burst Balloons, Palindrome Partitioning II, Matrix Chain Multiplication, and Longest Palindromic Subsequence.
• Master this recurrence and you have the template for every standard O(n^3) interval DP that appears at FAANG senior loops.