Strange Printer — Hard Problem & Solution

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 <= 100
• s consists of lowercase English letters.

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

1. Set dp[i][i] = 1.
2. For increasing lengths, start with dp[i][j] = dp[i][j-1] + 1.
3. For each k from i to j-1 with s[k] == s[j], take dp[i][k] + dp[k+1][j-1].
4. 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], not s[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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Number of Ways to Separate Numbers Hard
• Form Largest Integer With Digits That Add up to Target Hard
• Restore the Array Hard
• Special Binary String Hard
• Count Different Palindromic Subsequences Hard
• Smallest K-Length Subsequence With Occurrences of a Letter Hard