Description

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.

Input Format

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 Format

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

AAAAA

1

RGBGR

3

Hint

$40\%$ of the testdata satisfies $1 \le n \le 10$.

$100\%$ of the testdata satisfies $1 \le n \le 50$.

Translated by ChatGPT 5