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

- Printer can print consecutive identical characters in one go.
- 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**:

- Will try every option and choose the best one.
- 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
- 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.
- (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)
- Each option will produce a result, choose a minimum among those.
- See the diagram below for more understanding.

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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: " + (end–startTime)/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**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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: " + (end–startTime)/1000 + " seconds"); | |

} | |

} |

**Output**:

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