# 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.

Example 1:

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

Example 2:

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

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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[n - 1];
}
}
``````

O(N3)

O(N2)