557. The Printer That Prints Runs

A printer can only do one thing per turn: choose a character and a CONTIGUOUS range, and print that character across the whole range, overwriting whatever was there.

Starting from a blank strip, print the given string in the fewest turns.

aaabbb -> 2 print aaaaaa, then bbb over the right half aba -> 2 print aaa, then b in the middle abab -> 3

## Collapse the runs first

Two adjacent equal characters can always be printed by the same stroke, so a run of k identical characters costs exactly what a single one of them costs.

Replacing every maximal run by one character therefore changes nothing about the answer, and it shrinks the input. aaabbb becomes ab, which answers 2, and aaa becomes a, which answers 1.

That step is not merely an optimisation: without it the recurrence below still works, but the reasoning about "the same character appearing again later" becomes cluttered by neighbours that were never distinct.

## The key observation

Consider the first character of a range. Its stroke has to happen at some point, and it can be EXTENDED to cover any later occurrence of the same character, at no extra cost.

So either that stroke covers only position i, or it is shared with some later position k holding the same character.

dp[i][j] = 1 + dp[i+1][j] its own stroke dp[i][j] = min over k in (i, j] with t[k] == t[i] of dp[i+1][k-1] + dp[k][j] share the stroke with k

## Why sharing costs nothing extra

If the stroke that prints position i is stretched to reach k, everything strictly between them gets overwritten afterwards by the strokes counted in dp[i+1][k-1].

So the shared stroke is already paid for inside dp[k][j], and the two pieces add without a plus one. That missing plus one is the whole saving, and writing it as 1 + dp[i+1][k-1] + dp[k][j] gives an answer that is too large on every string with a repeat.

aba answers 2 and is the smallest case that shows it: a solution charging for both a strokes answers 3.

## Fill by length, as always

dp[i][j] reads dp[i+1][j], dp[i+1][k-1] and dp[k][j], all shorter ranges.

## Boundaries

A single character answers 1. abc answers 3, since no character repeats and nothing can be shared.

aabbaa collapses to aba and answers 2, which is the check that collapsing and the sharing rule work together.

abcba answers 3: print aaaaa, then bbb in the middle, then c. The two as share and the two bs share.

## Cost

Time O(n^3) after collapsing. Space O(n^2).

Constraints - `1 ≤ length of the string ≤ 100` - the string contains only lowercase letters