P4170 [CQOI2007] Coloring

Suppose you have a wooden board of length $5$, initially unpainted. You want to paint its $5$ unit segments red, green, blue, green, and red, respectively, represented by a length-$5$ string: $\texttt{RGBGR}$. Each time, you may paint a consecutive segment of the board with a given color, and later paint covers earlier paint. For example, first paint $\texttt{RRRRR}$, then paint $\texttt{RGGGR}$, and finally paint $\texttt{RGBGR}$ to reach the target. Use as few painting operations as possible to reach the target.

The input contains a single line with a string of length $n$, which is the painting target. Every character is an uppercase letter; different letters denote different colors, and the same letters denote the same color.

Output a single line with one number: the minimum number of painting operations.

$40\%$ of the testdata satisfies $1 \le n \le 10$. $100\%$ of the testdata satisfies $1 \le n \le 50$. Translated by ChatGPT 5