Dynamic programming – Printer Problem

Objective:  Given a printer which can perform only 2 operations-

  1. Printer can print consecutive identical characters in one go.
  2. It can replace consecutive characters by consecutive identical characters at any position.

You are given a string input with some characters. Write an algorithm to find the minimum number of printer operations required to print the input string.

Examples:

Input: aabbcc
Output: 3
(operation 1: print ‘aa’, operation 2: print ‘bb’, operation 3: print ‘cc’)

Input: aabbccaa
Output: 3
(Operation 1: print ‘aaaaaaaa’, operation 2: replace ‘aa’ with ‘bb’ in index 2 and 3, operation 3: replace ‘aa’ with ‘cc’ in index 4 and 5)

Reference: https://leetcode.com/problems/remove-boxes/description/

Approach:

This problem is similar to “Remove boxes” problem. We will try to club identical characters so that printing them all together will minimize the total number of operations.

Take the example input: “aba”. If we take out ‘b’ from the input string, the remaining string will be “aa” which can be printed in one operation. One thing is left is ‘b’ which can be printed by replace operation.  So when taking ‘b’ out, print ‘a’ instead and later replace it with ‘b’.

Recursion:

  1. Will try every option and choose the best one.
  2. Start from index 0, pick the continuous identical characters possible, add 1 to the total operations(either print operation or replace operation) and solve rest of the string using recursion
  3. Leave the option chosen in the step 2 and follow the same approach taken in step 2 starting from index where step 2 has ended. Solve the remaining string (which includes the option from step 2) recursively.
  4. (Do not worry about printing the one character in place of another if that gives the longer continuous identical characters since in next round of iteration we will replace it with the right character using replace operation and add 1 to total operation)
  5. Each option will produce a result, choose a minimum among those.
  6. See the diagram below for more understanding.

 

Code:

public class StrangePrinterRecursion {
public int print(String input){
int operations = input.length();
//base case
if(input==null || input.length()==0)
return 0;
int size = input.length();
if(size==1)
return 1;
int start_index=0;
int end_index =0;
while(start_index<size){
char c = input.charAt(start_index);
while(end_index<size && c==input.charAt(end_index)){
end_index++;
}
//if end_index has reached to the end of the string means recursive call is required only for the 0 to start_index
if(end_index>=size) {
operations =Math.min(operations,print(input.substring(0, start_index)) + 1);
}
else {
//else recursive call to rest of the string left
operations = Math.min(operations,print(input.substring(0, start_index) + input.substring(end_index, size)) + 1);
}
//put the start_index a the current end_index for the next iteration
start_index=end_index;
}
return operations;
}
public static void main(String[] args) {
StrangePrinterRecursion s = new StrangePrinterRecursion();
String input = "aabbccaa";
long startTime = System.currentTimeMillis();
System.out.println("Minimum Operations: " + s.print(input));
long end = System.currentTimeMillis();
System.out.println("Time taken: " + (endstartTime)/1000 + " seconds");
}
}


Dynamic Programming:

If we look closely the diagram above we are solving many sub problems recursively. Here we will use Top-down approach of dynamic programming. We will use Hash Map to store the sub problems results and whenever we make a recursive call, first check if the sub problem is already solved, if yes then use it.

Code:

import java.util.HashMap;
public class StrangePrinterDP {
HashMap<String,Integer> map = new HashMap<String, Integer>();
public int print(String input) {
int operations = input.length();
//base case
if (input == null || input.length() == 0)
return 0;
//check if we have already solved the problem
if(map.containsKey(input)){
return map.get(input);
}
int size = input.length();
if (size == 1)
return 1;
int start_index = 0;
int end_index = 0;
while (start_index < size) {
char c = input.charAt(start_index);
while (end_index < size && c == input.charAt(end_index)) {
end_index++;
}
//if end_index has reached to the end of the string means recursive call is required only for the 0 to start_index
if (end_index >= size) {
operations = Math.min(operations, print(input.substring(0, start_index)) + 1);
} else {
//else recursive call to rest of the string left
operations = Math.min(operations, print(input.substring(0, start_index) + input.substring(end_index, size)) + 1);
}
//put the start_index a the current end_index for the next iteration
start_index = end_index;
}
//store the result for future
map.put(input,operations);
return operations;
}
public static void main(String[] args) {
StrangePrinterDP s = new StrangePrinterDP();
String input = "aabbccaa";
long startTime = System.currentTimeMillis();
System.out.println("Minimum Operations: " + s.print(input));
long end = System.currentTimeMillis();
System.out.println("Dynamic Programming – Time taken: " + (endstartTime)/1000 + " seconds");
}
}


Output:

Minimum Operations: 3
Dynamic Programming - Time taken: 0 seconds