# Strange Printer Problem

## Description

LeetCode Problem 664.

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:

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

Example 2:

``````1
2
3
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.

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
private:
int f;

private:
// f[i][j] represents the minumum turns to print the sequence from i to j.
// The transition function is:
// f[i][j] = min(f[i][k] + f[k+1][j-1]) for each k where i<k<j and s[k]=s[j]
// f[i][j] = f[i][j-1] + 1
// And the border condition: f[i][j] = 0 where i>j
int dfs(const std::string& s, int l, int r) {
if (l > r)
return 0;
if (f[l][r])
return f[l][r];

f[l][r] = dfs(s, l, r - 1) + 1;
for (int i = l; i < r; ++i) {
if (s[i] == s[r]) {
f[l][r] = std::min(f[l][r], dfs(s, l, i) + dfs(s, i + 1, r - 1));
}
}
return f[l][r];
}

public:
int strangePrinter(std::string s) {
memset(f, 0, sizeof(f));
int len = (int)s.size();
return dfs(s, 0, len - 1);
}
};
``````