Skip to main content

664. Strange Printer

hard

Given a string of characters, return the minimum number of printer passes required, where each pass paints a single character across any contiguous range. Pure interval DP — dp[i][j] depends on every split between i and j.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There is a strange printer with the following two special properties: The printer can only print a sequence of the same character each time. At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters. Given a string s, return the minimum number of turns the printer needed to print it.

Constraints

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

Examples

Example 1

Input
s = "aaabbb"
Output
2

Explanation: Print 'aaa' first and then print 'bbb'.

Example 2

Input
s = "aba"
Output
2

Explanation: Print 'aaa' first and then print 'b' from the second place of the string, which will cover the existing character 'a'.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Interval DP. dp[i][j] = minimum turns to print s[i..j].

Hint 2

Base: dp[i][i] = 1.

Hint 3

If s[i] == s[j], then dp[i][j] = dp[i][j-1] (paint s[i] over the whole interval; the trailing s[j] piggybacks on that pass).

Hint 4

Otherwise try every split point k in [i, j-1]: dp[i][j] = min over k of dp[i][k] + dp[k+1][j].

Hint 5

Fill in increasing interval length.

Solution approach

Reveal approach

Interval DP. dp[i][j] is the minimum number of turns to print s[i..j]. Initialize dp[i][i] = 1 for every i. Iterate interval length from 2 to n, and for each (i, j): start with dp[i][j] = dp[i][j-1] + 1 (print s[i..j-1] then add a fresh stroke for s[j]). Then for every k in [i, j-1] where s[k] == s[j], take dp[i][j] = min(dp[i][j], dp[i][k] + (k + 1 <= j - 1 ? dp[k+1][j-1] : 0)) — merging the trailing s[j] into the stroke that painted s[k]. Return dp[0][n-1]. A common preprocessing step collapses runs of identical characters into single ones, which cuts the constant factor.

Complexity

Time
O(n^3)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • interval-dp
  • string-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Strange Printer and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →