Problem Description

You are given a string $ S $ consisting of lowercase English letters.

This string is formed by concatenating one or more strings such that the first character of each string is the smallest character in alphabetical order within that string, similar to code.

Each original string does not contain multiple occurrences of the first character.

What is the minimum number of such strings that could have been concatenated to form $ S $?

Input Format

The input is given from the standard input in the following format:

$ S $

Output Format

Output the minimum number of strings that could be concatenated to form $ S $.

Sample Input and Output

Sample Input #1

codethanksfes

Sample Output #1

2

Sample Input #2

atcoder

Sample Output #2

1

Sample Input #3

aaa

Sample Output #3

3

Notes/Hints

Constraints

• $1 \leq |S| \leq 10^5$
• $ S $ consists of lowercase English letters.

Sample Explanation 1

For example, codeth and anksfes can be concatenated to form the string.

Sample Explanation 2

atcoder satisfies the condition.

见题面 Input 部分

见题面 Output 部分