p77 — Strange Printer

Source: LeetCode 664 · Hard · Topics: DP, Interval DP, String Companies (2024–2025): Google (high), Amazon (medium-high), Meta (medium), Microsoft (medium) Loop position: The interval DP with the “skip matching endpoint” optimization. Natural recurrence is O(n⁴); the insight that s[i] == s[k] lets you absorb one print cuts it to O(n³). Tests whether the candidate can see the matching-endpoint structure.

1. Quick Context

A printer prints sequences of the same character only. To print “aab” requires: print “aaa”, overprint position 2 with “b” → 2 turns. Given a string s, find minimum number of turns to print it.

Strategy: Interval DP. dp[i][j] = min turns to print s[i..j]. Recurrence:

  • Base: dp[i][i] = 1.
  • General: dp[i][j] = dp[i+1][j] + 1, then try improvements: for each k in i+1..j with s[k] == s[i]: dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]).

O(n³).

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/strange-printer/

STOP. 45-min timer. The matching-endpoint insight is hard to find cold.

3. Prerequisite Concepts

  • Interval DP (MCM, Burst Balloons).
  • Why splitting on intervals beats splitting on prefixes for non-overlapping subproblems.
  • Recognizing the “matching endpoints absorb a print” pattern.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Min printer turns where each turn paints a contiguous block of the SAME char (which may be later overwritten in a sub-region).

2. Clarify: Each turn paints any contiguous range; later turns can overwrite. The order matters in the sense that we count turns, not positions.

3. Examples: “aaabbb” → 2 (print ‘a’×3 then ‘b’×3). “aba” → 2 (print ‘aaa’, then ‘b’ at middle). “aabbaa” → 2 (print ‘aaaaaa’, then ‘bb’ in middle).

5. Brute force: Try all sequences of (range, char) operations. Exponential.

6. Target: O(n³) interval DP.

7. Pattern: Interval DP with shared-endpoint merging.

8. Develop: see solution.py.

9. Test: single char; all same; alternating; reduce-by-merge example “aabbaa” should be 2 not 3.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 The naive recurrence (without the insight)

dp[i][j] = min over k in [i, j) of dp[i][k] + dp[k+1][j]. O(n³) splits × O(n²) intervals = O(n⁴). Often TLE.

6.2 The matching-endpoint insight

Observation: if s[i] == s[j], then dp[i][j] = dp[i][j-1]. Why? Print s[i..j-1] optimally; the same print stroke that painted s[i] can be extended to cover position j (since s[j] = s[i]). No extra turn.

Generalized: dp[i][j] = dp[i+1][j-1] + (1 if s[i] != s[j] else 0) — not quite, but close. The clean form: start with dp[i][j] = dp[i+1][j] + 1 (print s[i] alone, then the rest); then for each k in i+1..j with s[k] == s[i], try dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k][j]) — the stroke painting s[i] extends to also cover s[k], so we don’t count an extra turn at k.

6.3 Why “fix the first char, scan for matches”

When painting s[i], the printer paints a contiguous range. Anything inside that range that’s a DIFFERENT char gets overprinted later. So we only need to think about which OTHER positions of the SAME char s[i] share the same paint stroke as s[i]. For each such k, the segment between (i+1..k-1) is printed independently AFTER, and the segment (k..j) is printed independently of i. The +0 (not +1) for the matching k is the savings.

6.4 String reduction trick

Collapse consecutive duplicates first: “aaabbb” → “ab”. Doesn’t change the answer (one stroke handles consecutive duplicates). Speeds up by collapsing degenerate input.

6.5 Fill order

Length-major: outer loop = interval length 1..n; inner = i with j = i + length - 1. Ensures dp[i+1][j], dp[i+1][k-1], dp[k][j] are all already computed.

6.6 Connection to other interval-DP problems

  • LC 312 Burst Balloons: split on LAST burst.
  • LC 1547 Min Cost to Cut a Stick: split on WHICH cut to make first.
  • LC 132 Palindrome Partitioning II: cuts DP on top of palindrome precomputation.
  • LC 1000 Min Cost to Merge Stones: K-merge interval DP.

Each is an O(n³) interval DP with a problem-specific split rule.

6.7 Generalization: this is “polygon triangulation”

Treat the string as vertices on a polygon. Each “stroke” is a triangle (or generalization). The cost is the number of strokes. This is exactly the polygon-triangulation DP family — Knuth-Yao quadrangle inequality applies in some variants and can drop O(n³) to O(n²).

7. Anti-Pattern Analysis

  1. Greedy “print biggest contiguous same-char run first” — fails on “aba” (greedy paints “a” then “b” then “a” = 3 turns; optimal is 2).
  2. Naive O(n⁴) interval split without the matching-endpoint insight — TLE for n=100.
  3. Forget the +1 baseline dp[i][j] = dp[i+1][j] + 1 — recurrence becomes a strict improvement loop with no base.
  4. Don’t collapse consecutive duplicates — wastes time; doesn’t break correctness but burns the time budget.
  5. Wrong fill order — reading uninitialized cells.
  6. Confusing this with LC 546 (Remove Boxes) — different recurrence (3D state with “k same-color blocks to the right”).

8. Skills & Takeaways

  • Interval DP archetype recognition.
  • “Matching endpoint absorbs one operation” insight.
  • Length-major fill order.
  • String preprocessing (collapse duplicates) as O(n) speedup.

9. When to Move On

  • Solve cold in 35 min with O(n³) interval DP.
  • Articulate the matching-endpoint savings cleanly.
  • State the family (Burst Balloons, MCM, Cut a Stick, Merge Stones).
  • Mention polygon-triangulation / Knuth-Yao framing at Staff+.

10. Company Context

  • Google: L5/L6; interval DP probe.
  • Amazon: L6; tests pattern recognition.
  • Meta: E5; appears in onsite rotation.
  • Microsoft: L65; less common.

Scorecard for strong: “Recognized interval DP, found matching-endpoint savings unprompted, O(n³) cold, correct fill order, mentioned the interval-DP family and polygon-triangulation generalization.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
ApproachGreedyNaive O(n⁴)O(n³) with matching-endpoint cold+ cites family + polygon triangulation
InsightNoneAfter hintCold+ proves savings rigorously
Fill orderWrongAfter failingLength-major cold+ mentions Knuth-Yao bound
GeneralizationNoneNoneCites family+ Eertree / suffix-automaton tangent at Principal

12. Level Delta

  • Mid (L4): Naive interval DP after hints; O(n⁴) accepted on small inputs.
  • Senior (L5): O(n³) with matching-endpoint savings cold + correct fill order + collapses duplicates.
  • Staff (L6): + cites Burst Balloons / MCM / Cut a Stick family + polygon-triangulation framing.
  • Principal (L7+): + Knuth-Yao quadrangle inequality + O(n²) variants in specific structures + production string-processing library architecture.

13. Follow-up Q&A

Q1: What if the printer can paint NON-contiguous ranges? A1: Answer is just the number of distinct characters (one stroke per char). Trivial.

Q2: Variant: printer can only paint ranges of length ≤ K. A2: Add constraint to recurrence; range of valid k limited. Still O(n³).

Q3: Reconstruct the actual sequence of strokes. A3: Track parent pointer at each DP cell; backtrack from dp[0][n-1].

Q4: What’s the connection to Burst Balloons? A4: Both are interval DP. Burst Balloons splits on “last burst inside interval.” Strange Printer splits on “which other matching char shares the stroke.” Both O(n³).

Q5: Knuth-Yao optimization? A5: When the recurrence satisfies the quadrangle inequality, the optimal split point is monotonic in (i,j), allowing amortized O(n²) total. Doesn’t apply directly here without modification.

14. Solution Walkthrough

See solution.py:

  • strange_printer_dp — iterative O(n³) with matching-endpoint optimization.
  • strange_printer_memo — top-down with @lru_cache.
  • strange_printer_brute — try all stroke sequences (oracle for small).

15. Beyond the Problem

Principal code review: “Strange Printer is the canonical ‘interval DP with absorption’ problem. The matching-endpoint insight (s[i] == s[k] lets one stroke serve both) is the same shape as ‘polygon triangulation skip’ — when two vertices share a property, the triangle linking them costs nothing extra. This pattern recurs in compiler optimizations (common subexpression elimination — same expression in multiple places shares one computation), in graph drawing (shared crossings), and in database query planning (shared subtrees in plan trees). At the Staff+ bar, articulate this absorption as the general principle: ‘when the cost function exhibits sub-additivity over shared structure, hoist the shared structure into the recurrence.’ The interval-DP family — Burst Balloons, MCM, Cut a Stick, Strange Printer, Merge Stones — is one of the most-tested archetypes precisely because it forces this kind of structural thinking.”