Minimum Number of Non-Empty Disjoint Segments

Split the string into non-empty, disjoint contiguous segments so that each character belongs to exactly one segment and no character repeats within a segment. Find the minimum number of segments.

输入格式

One line containing a lowercase string of length 1..200000.

输出格式

Output one integer, the answer.

样例 1

输入：

bcoc

输出：

2

样例 2

输入：

abdaa

输出：

3

样例 3

输入：

abcdefghijklmnopqrstuvwxyz

输出：

1

样例说明

The examples give 2, 3 and 1 respectively.