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 <= 100`
• `s` consists 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>
}
``````
Copy The Code &

Input

cmd
s = "aaabbb"

Output

cmd
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)
``````
Copy The Code &

Input

cmd
s = "aaabbb"

Output

cmd
2