Strange Printer

Hard Dynamic Programming Interval DP Original on LeetCode

Reported atIntuitInMobi

Strange Printer is a hard dynamic programming problem solved with the interval dp pattern. The best approach, optimal (interval dp), runs in O(n³) time and O(n²) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (plain recursion over ranges) up.

Problem

A printer has two quirks: in one turn it prints a run of a single repeated character, and that run can start and end anywhere, overwriting whatever was already printed in those positions.

Starting from an empty line, return the minimum number of turns needed to print the string s exactly.

Examples

Example 1

Input
s = "xyx"
Output
2
Why
Print "xxx" first, then print 'y' over the middle cell.

Example 2

Input
s = "ppqqp"
Output
2
Why
Print "ppppp", then overwrite positions 2 to 3 with "qq".

Example 3

Input
s = "abcd"
Output
4
Why
All letters differ, so every character needs its own turn.

Constraints

  • 1 <= s.length <= 100
  • s contains only lowercase English letters.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (plain recursion over ranges)ExponentialO(n)
Optimal (interval DP)O(n³)O(n²)

1Brute force (plain recursion over ranges)

TimeExponentialThe same ranges are solved again and again across branches.
SpaceO(n)Only the recursion stack, at most n frames deep.

Define f(i, j) as the minimum turns to print s[i..j]. Either the last character gets a stroke of its own, f(i, j - 1) + 1, or it shares the stroke of an earlier equal character s[k], which splits the work into f(i, k) and f(k + 1, j - 1). Try every option recursively without remembering results.

  1. f(i, j) = 0 if i > j.
  2. best = f(i, j - 1) + 1.
  3. For each k in [i, j - 1] with s[k] == s[j]: best = min(best, f(i, k) + f(k + 1, j - 1)).
  4. Return f(0, n - 1).
class Solution {
    public int strangePrinter(String s) {
        return solve(s, 0, s.length() - 1);
    }

    private int solve(String s, int i, int j) {
        if (i > j) return 0;
        int best = solve(s, i, j - 1) + 1;
        for (int k = i; k < j; k++) {
            if (s.charAt(k) == s.charAt(j)) {
                best = Math.min(best, solve(s, i, k) + solve(s, k + 1, j - 1));
            }
        }
        return best;
    }
}

2Optimal (interval DP)

TimeO(n³)O(n²) cells, each scanning up to n split points.
SpaceO(n²)The n x n table.

The recursion only ever asks about O(n²) ranges, so fill a table dp[i][j] from short ranges to long ones. Each cell tries the 'own stroke' option and every split point k where s[k] matches s[j].

  1. dp[i][i] = 1 for every i.
  2. For i from n - 1 down to 0, for j from i + 1 to n - 1: dp[i][j] = dp[i][j - 1] + 1.
  3. For each k in [i, j - 1] with s[k] == s[j]: dp[i][j] = min(dp[i][j], dp[i][k] + (k + 1 <= j - 1 ? dp[k + 1][j - 1] : 0)).
  4. Return dp[0][n - 1].
class Solution {
    public int strangePrinter(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = dp[i][j - 1] + 1;
                for (int k = i; k < j; k++) {
                    if (s.charAt(k) == s.charAt(j)) {
                        int right = k + 1 <= j - 1 ? dp[k + 1][j - 1] : 0;
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + right);
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
}

Edge cases to test

  • A single character, or a string of one repeated character (answer 1)
  • All characters different (answer n)
  • Runs of equal letters, which behave exactly like one letter
  • Nested patterns like "abacaba" where one long stroke is overwritten many times

Hints

Hint 1

Think about the stroke that prints the last character s[j] of a range. It may also cover earlier positions holding the same letter.

Hint 2

Let f(i, j) be the fewest turns for s[i..j]. Printing s[j] on its own costs f(i, j - 1) + 1.

Hint 3

If some s[k] == s[j] with i <= k < j, one stroke can print both, giving f(i, k) + f(k + 1, j - 1). Take the minimum over all such k, using an interval DP by increasing length.

FAQ

What is the best time complexity for Strange Printer?

Optimal (interval DP) runs in O(n³) time and O(n²) extra space. O(n²) cells, each scanning up to n split points.

Which pattern does Strange Printer use?

It is a dynamic programming problem that uses the interval dp pattern. Other problems with the same pattern: Matrix Chain Multiplication, Burst Balloons, Predict the Winner.

Is there a brute force solution for Strange Printer?

Yes. Brute force (plain recursion over ranges) takes Exponential time and O(n) space. Define f(i, j) as the minimum turns to print s[i..j].

Which edge cases should I test for Strange Printer?

A single character, or a string of one repeated character (answer 1); All characters different (answer n); Runs of equal letters, which behave exactly like one letter; Nested patterns like "abacaba" where one long stroke is overwritten many times.