HardStringDynamic Programming

Strange Printer

1 approach, code in every language

A peculiar printer can only perform one kind of operation: in a single action it prints a solid run of one repeated character, and that run overwrites whatever characters occupied those positions before.

Given a target string s, you want to reproduce it exactly. Each action lays down a contiguous block of identical letters, possibly covering characters printed earlier.

Return the fewest number of printing actions required to end up with the string s.

Example 1

Input: s = "aaabbb"

Output: 2

Print "aaa" first, then print "bbb" to the right; two actions suffice.

Example 2

Input: s = "aba"

Output: 2

Print "aaa" as one run, then overwrite the middle character with "b" to get "aba".

Constraints

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

Range DP with Character Merging

Define dp[i][j] as the minimum prints for s[i..j] and merge whenever a matching character lets one run cover two segments.

Loading animation…

Intuition

Printing s[j] can always be tacked on as its own fresh run, giving the baseline dp[i][j] = dp[i][j-1] + 1. The savings come when some earlier position k in the range shares the same character as s[j]: the run that prints s[k] can be extended rightward to also paint s[j] for free. In that case the interval splits into dp[i][k] (which already pays for the shared character) plus the untouched middle dp[k+1][j-1], and the print for s[j] is absorbed. We try every such matching k and keep the cheapest. Filling by increasing interval length ensures all smaller ranges are ready before we combine them.

Algorithm walkthrough

1Let dp[i][j] be the minimum prints needed to produce the substring s[i..j]; set every single character dp[i][i] = 1.
2Process i from right to left and j from i+1 upward so shorter intervals are already solved.
3Start with dp[i][j] = dp[i][j-1] + 1, treating s[j] as an independent new run.
4For each k in [i, j-1] with s[k] == s[j], extend s[k]'s run to cover s[j]: candidate = dp[i][k] + (k+1 <= j-1 ? dp[k+1][j-1] : 0).
5Take the minimum over all such candidates, then return dp[0][n-1] for the whole string.

Implementation

class Solution:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n):
                dp[i][j] = dp[i][j - 1] + 1
                for k in range(i, j):
                    if s[k] == s[j]:
                        right = dp[k + 1][j - 1] if k + 1 <= j - 1 else 0
                        dp[i][j] = min(dp[i][j], dp[i][k] + right)
        return dp[0][n - 1]

Time

O(n^3)

Space

O(n^2)

There are O(n^2) substrings and each scans O(n) split points k; the DP table stores one value per (i, j).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Sign Press Passes is our own problem on the technique behind Strange Printer: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free