Be the first user to complete this post

  • 0
 Add to List
Hard

245. Dynamic programming – Printer Problem | Leetcode

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)

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.

Output:

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.

Output:

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

Reference: Leetcode

Related Problems: