This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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

- 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 places, and will cover the original existing characters.

Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

**Example 1:**

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

**Example 2:**

Input:"aba"Output:2Explanation:Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.

**Hint**: Length of the given string will not exceed 100.

b'

\n\n#### Approach #1: Dynamic Programming [Accepted]

\n

\n

'
**Intuition**

It is natural to consider letting `dp(i, j)`

be the answer for printing `S[i], S[i+1], ..., S[j]`

, but proceeding from here is difficult. We need the following sequence of deductions:

- \n
- \n
Whatever turn creates the final print of

\n`S[i]`

might as well be the first turn, and also there might as well only be one print, since any later prints on interval`[i, k]`

could just be on`[i+1, k]`

. \n - \n
Say the first print is on

\n`[i, k]`

. We can assume`S[i] == S[k]`

, because if it wasn\'t, we could print up to the last occurrence of`S[i]`

in`[i, k]`

for the same result. \n - \n
When correctly printing everything in

\n`[i, k]`

(with`S[i] == S[k]`

), it will take the same amount of steps as correctly printing everything in`[i, k-1]`

. This is because if`S[i]`

and`S[k]`

get completed in separate steps, we might as well print them first in one step instead. \n

**Algorithm**

With the above deductions, the algorithm is straightforward.

\nTo compute a recursion for `dp(i, j)`

, for every `i <= k <= j`

with `S[i] == S[k]`

, we have some candidate answer `dp(i, k-1) + dp(k+1, j)`

, and we take the minimum of these candidates. Of course, when `k = i`

, the candidate is just `1 + dp(i+1, j)`

.

To avoid repeating work, we memoize our intermediate answers `dp(i, j)`

.

**Complexity Analysis**

- \n
- \n
Time Complexity: where is the length of

\n`s`

. For each of possible states representing a subarray of`s`

, we perform work iterating through`k`

. \n - \n
Space Complexity: , the size of our

\n`memo`

. \n

\n

Analysis written by: @awice.

\n