Minimum Operations to Remove Characters in Frequency Order (Find Min Deletions :)

Each time, choose a non-empty contiguous substring of the current string; it can be deleted only if all of its characters are the same. After a deletion the left and right parts are joined, which may form a new contiguous run of the same character. Find the minimum number of deletions needed to empty the string. The frequency order mentioned in the title adds no extra requirement on the operations; deletions are not ordered by character frequency.

输入格式

The input is a JSON string. On this site 0≤length≤200, characters are counted as Unicode characters, and the empty string is valid. Whitespace and non-ASCII characters in the JSON string must be escaped, with a space written as \u0020.

输出格式

Output a single integer, the answer.

样例 1

输入：

"abaca"

输出：

3

样例 2

输入：

"aba"

输出：

2

样例 3

输入：

""

输出：

0

样例说明

The answers are 3, 2 and 0. For abaca, delete b and c first, then delete aaa in one go; counting the original same-character runs, as the source does, wrongly gives 5, so the joining after deletions cannot be ignored.