Strange Printer

Hard
1057.

Strange Printer

Strange Printer is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Meta interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var strangePrinter = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Strange Printer — Solution in Python, Java & C++

Strange Printer solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Strange Printer is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Meta interviews.

  • Difficulty: Hard
  • Topics: Strings, Dynamic Programming
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Strange Printer

  1. Hint 1

    Think of the last character. Printing it can be merged with an earlier turn that printed the same character.

  2. Hint 2

    dp[i][j] = the minimum turns for s[i..j].

  3. Hint 3

    Start from dp[i][j-1] + 1, then try merging with each earlier position k where s[k] == s[j].

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]

Java

public static int strangePrinter(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = dp[i][j - 1] + 1;
            for (int k = i; k < j; k++) {
                if (s.charAt(k) == s.charAt(j)) {
                    int 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];
}

C++

int strangePrinter(string s) {
    int n = (int) s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = dp[i][j - 1] + 1;
            for (int k = i; k < j; k++) {
                if (s[k] == s[j]) {
                    int inner = k + 1 <= j - 1 ? dp[k + 1][j - 1] : 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming