Strange Printer

This page explains Java solution to problem Strange Printer using Dynamic Programming algorithm.

Problem Statement

There is a strange printer with the following two special requirements:

• 1. The printer can only print a sequence of the same character each time.
• 2. At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.

Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Input: "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".

Input: "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'.

Solution

package com.vc.hard;

class StrangePrinter {
    public int strangePrinter(String s) {
        if(s == null || s.length() == 0) return 0;

        int n = s.length();
        int[][] dp = new int[n][n];
        for(int len = 0; len < n; len++) {
            for(int from = 0; from + len < n; from++) {
                int to = from + len;
                if(len == 0) dp[from][to] = 1;
                else {
                    dp[from][to] = Integer.MAX_VALUE;
                    for(int middle = from; middle < to; middle++) {
                        dp[from][to] = Math.min(dp[from][to],
                                dp[from][middle] + dp[middle + 1][to]);
                    }
                    if(s.charAt(from) == s.charAt(to)) dp[from][to]--;
                }
            }
        }
        return dp[0][n - 1];
    }
}

Time Complexity

O(N³)

Space Complexity

O(N²)