Algorithm
Problem Name: 664. Strange Printer
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 <= 100sconsists of lowercase English letters.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const strangePrinter = function(s) {
// optimize
const arr = s.split('')
for(let i = 1; i < arr.length; i++) {
if(arr[i] === arr[i - 1]) arr[i - 1] = ''
}
s = arr.join('')
let n = s.length
let dp = new Array(n).fill(0).map(() => new Array(n).fill(0))
const help = (s, i, j) => {
if (i > j) return 0
if (dp[i][j] > 0) {
return dp[i][j]
}
let res = help(s, i, j - 1) + 1
for (let k = i; k < j; k++) {
if (s[k] === s[j]) {
res = Math.min(help(s, i, k) + help(s, k + 1, j - 1), res)
}
}
dp[i][j] = res
return res
}
return help(s, 0, n - 1>
}
Input
s = "aaabbb"
Output
2
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def strangePrinter(self, s):
memo = {}
def dp(i, j):
if i > j: return 0
if (i, j) not in memo:
ans = dp(i+1, j) + 1
for k in range(i+1, j+1):
if s[k] == s[i]:
ans = min(ans, dp(i, k-1) + dp(k+1, j))
memo[i, j] = ans
return memo[i, j]
return dp(0, len(s) - 1)
Input
s = "aaabbb"
Output
2