Strange Printer

Problem

Given a string s, return the minimum number of turns of a strange printer to print it; each turn prints one character over a contiguous range and may overwrite existing characters.

Use interval DP: start dp[i][j] at dp[i+1][j] + 1, and whenever s[k] equals s[i] for some k in the interval, merging the print of s[i] over that range can lower the cost. Return 0 for an empty string.

Hint

Reusing s[i] at position k lets the printer paint the middle first and s[i] later over a wider span.

Test cases

case 1

in: ["aaabbb"]

expected: 2

case 2

in: ["aba"]

expected: 2

case 3

in: ["abc"]

expected: 3

case 4

in: [""]

expected: 0

case 5

in: ["aaaa"]

expected: 1

case 6

in: ["abba"]

expected: 2

Starter codePython

def strange_printer(s):
    # Your code here
    pass

6 test cases · run your code against them in the editor