# LeetCode 664: Strange Printer

## Problem Restatement

We are given a string `s`.

There is a strange printer with two rules:

| Rule | Meaning |
|---|---|
| Same character only | In one turn, the printer can print only one repeated character |
| Overwrite allowed | A later turn can cover characters printed earlier |

The printer can choose any continuous segment of the string in one turn.

Return the minimum number of turns needed to print the whole string.

For example, to print:

```python
s = "aba"
```

we can first print:

```text
aaa
```

Then overwrite the middle character with:

```text
b
```

So the answer is `2`. The statement details match LeetCode 664: the printer prints a sequence of the same character and may overwrite existing characters.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A lowercase English string `s` |
| Output | Minimum number of turns needed |
| Operation | Print one repeated character over a continuous segment |
| Extra rule | New printing can cover old printing |

Example function shape:

```python
def strangePrinter(s: str) -> int:
    ...
```

## Examples

Consider:

```python
s = "aaabbb"
```

We can print `"aaa"` in one turn and `"bbb"` in another turn.

So the answer is:

```python
2
```

Now consider:

```python
s = "aba"
```

One optimal plan is:

```text
Turn 1: print "aaa"
Turn 2: print "b" at the middle position
```

So the answer is:

```python
2
```

Another example:

```python
s = "abc"
```

Each character is different. We need one turn for each character:

```text
a
b
c
```

So the answer is:

```python
3
```

## First Thought: Print Groups

A natural idea is to print each consecutive group separately.

For example:

```python
s = "aaabbb"
```

has two groups:

```text
aaa
bbb
```

So the answer is `2`.

But this does not always capture the best strategy.

For:

```python
s = "aba"
```

there are three groups:

```text
a
b
a
```

A group-based strategy would say `3`, but the real answer is `2`.

The printer can overwrite characters, so matching characters that are separated may still be printed together.

## Key Insight

This is an interval dynamic programming problem.

Let:

```python
dp[i][j]
```

mean:

```text
the minimum number of turns needed to print s[i:j+1]
```

The answer is:

```python
dp[0][n - 1]
```

For one character:

```python
dp[i][i] = 1
```

because a single character needs one print turn.

For a longer substring, we can start with a safe choice:

```text
print s[j] separately after printing s[i:j]
```

That gives:

```python
dp[i][j] = dp[i][j - 1] + 1
```

But if there is an earlier position `k` where:

```python
s[k] == s[j]
```

then the turn that prints `s[k]` can also print `s[j]`.

That may save one turn.

## Recurrence

For every substring `s[i:j+1]`, initialize:

```python
dp[i][j] = dp[i][j - 1] + 1
```

Then try every `k` from `i` to `j - 1`.

If:

```python
s[k] == s[j]
```

then we can combine the printing of `s[k]` and `s[j]`.

The candidate cost is:

```python
dp[i][k] + dp[k + 1][j - 1]
```

So:

```python
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j - 1])
```

The middle part `s[k+1:j]` must still be printed separately, but the final `s[j]` does not require its own new turn.

## Algorithm

1. Let `n = len(s)`.
2. Create an `n x n` DP table.
3. Set all `dp[i][i] = 1`.
4. Process substrings by increasing length.
5. For each substring `s[i:j+1]`:
   - Start with `dp[i][j - 1] + 1`.
   - Try every split position `k`.
   - If `s[k] == s[j]`, merge the print turn for those matching characters.
6. Return `dp[0][n - 1]`.

## Correctness

The state `dp[i][j]` considers only the substring from index `i` to index `j`.

For a single-character substring, one turn is necessary and sufficient.

For a longer substring, printing `s[j]` in a separate final turn after printing `s[i:j]` is always valid, so `dp[i][j - 1] + 1` is a correct upper bound.

If some earlier character `s[k]` equals `s[j]`, then the printer can use the same turn that prints `s[k]` to also print `s[j]`, because a turn may print a continuous segment of one character and later turns may overwrite the positions between them. The substring between `k` and `j` is handled separately by `dp[k + 1][j - 1]`.

The algorithm tries every possible matching position `k`, so it considers every possible way for the final character `s[j]` to share a print turn with an earlier equal character.

Since substrings are processed by increasing length, all smaller intervals used in the recurrence are already computed.

Therefore, each `dp[i][j]` is optimal, and `dp[0][n - 1]` is the minimum number of turns needed to print the whole string.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^3)` | There are `O(n^2)` intervals, and each tries up to `O(n)` positions |
| Space | `O(n^2)` | The DP table stores every interval |

The official constraint is small enough for this interval DP approach: `s.length <= 100`.

## Implementation

```python
class Solution:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1

                dp[i][j] = dp[i][j - 1] + 1

                for k in range(i, j):
                    if s[k] == s[j]:
                        middle = 0
                        if k + 1 <= j - 1:
                            middle = dp[k + 1][j - 1]

                        dp[i][j] = min(
                            dp[i][j],
                            dp[i][k] + middle,
                        )

        return dp[0][n - 1]
```

## Code Explanation

We create a square DP table:

```python
dp = [[0] * n for _ in range(n)]
```

Then initialize every one-character interval:

```python
for i in range(n):
    dp[i][i] = 1
```

A single character always takes one turn.

We process intervals by length:

```python
for length in range(2, n + 1):
```

For each interval, compute its right endpoint:

```python
j = i + length - 1
```

The default choice is to print the final character separately:

```python
dp[i][j] = dp[i][j - 1] + 1
```

Then we look for an earlier equal character:

```python
for k in range(i, j):
    if s[k] == s[j]:
```

If `s[k] == s[j]`, the character at `j` can share the same printing turn as the character at `k`.

The middle interval may be empty:

```python
middle = 0
if k + 1 <= j - 1:
    middle = dp[k + 1][j - 1]
```

Then we update the best answer:

```python
dp[i][j] = min(
    dp[i][j],
    dp[i][k] + middle,
)
```

Finally:

```python
return dp[0][n - 1]
```

returns the minimum number of turns for the whole string.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.strangePrinter("aaabbb") == 2
    assert s.strangePrinter("aba") == 2
    assert s.strangePrinter("abc") == 3
    assert s.strangePrinter("aaa") == 1
    assert s.strangePrinter("abab") == 3
    assert s.strangePrinter("abaaba") == 3

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"aaabbb"` | Standard example with two character blocks |
| `"aba"` | Confirms overwrite can reduce turns |
| `"abc"` | Different characters require separate turns |
| `"aaa"` | Same repeated character needs one turn |
| `"abab"` | Checks separated repeated characters |
| `"abaaba"` | Checks larger interval merging |