664. Strange Printer

Description

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

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

Given a string s, return the minimum number of turns the printer needed to print it.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= s.length <= 100
• s consists of lowercase English letters.

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n³)
• Space complexity: O(n²)

 

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
const strangePrinter = function (s) {
  const n = s.length;
  const memo = new Array(n)
    .fill('')
    .map(_ => new Array(n).fill(0));

  const turnPrinter = (left, right) => {
    if (left > right) return 0;
    if (memo[left][right]) return memo[left][right];

    let result = turnPrinter(left + 1, right) + 1;

    for (let index = left + 1; index <= right; index++) {
      if (s[left] !== s[index]) continue;

      const turnTimes = turnPrinter(left, index - 1) + turnPrinter(index + 1, right);

      result = Math.min(turnTimes, result);
    }
    return (memo[left][right] = result);
  };

  return turnPrinter(0, n - 1);
};