Minimum Paint Operations on a Wooden Board

You are given a wooden board divided into n unit segments. Initially, the board is uncolored. Your task is to paint the board to match a target pattern represented by a string s of length n where each character represents a color (for example, 'R' for red, 'G' for green, 'B' for blue). In one painting operation, you can choose a contiguous segment of the board and paint it with one color. Note that if a segment is repainted later, the new color overrides the previous one.

For example, consider the target pattern for n=5: \[ \texttt{RGBGR} \] One way to achieve this is:

1. Paint the entire board with red: RRRRR.
2. Paint the middle three segments with green: RGGGR.
3. Paint the third segment with blue: RGBGR.

The goal is to achieve the target pattern in as few painting operations as possible. The answer for the above example is 3.

Hint: This problem is analogous to the "Strange Printer" problem and can be solved using dynamic programming. The typical recurrence is:

[ dp[i][j] = \min_{i \le k < j} (dp[i][k] + dp[k+1][j]) ]

with an additional optimization if \( s[k] = s[j] \), then one may combine operations. All formulas must be rendered in LaTeX format.

inputFormat

The input consists of a single line containing a string s which represents the target color pattern. The length of s (n) satisfies 1 ≤ n ≤ 200. The string only contains uppercase letters representing colors (e.g., R, G, B).

outputFormat

Output a single integer: the minimum number of painting operations required to achieve the target color pattern.

sample

RGBGR

3