Problem C
USB Keyboard
Most modern keyboards are connected to a computer by USB, presenting themselves as USB HID (Human Interface Devices) keyboards. HID keyboards communicate keypresses to the software reading inputs through a series reports. A report consists of up to six keypress values, describing what keys are currently pressed on the keyboard. For example, if you simultaneously hold down the keys coding on the keyboard, the report will contain the values representing those six letters.
On some operating systems, these reports are interpreted not in the order in which these values are sent in the report, but rather in increasing alphabetical order. Thus, a report containing the keys coding would actually cause the software to input the characters in the order cdgino.
You are creating a small USB device acting as a keyboard, meant to as quickly as possible input a long text string into the computer. Can you write a program that, given such a text string, determines the number of USB HID reports needed by the device to input the entire string?
Input
The first line contains the text string. It has between $1$ and $100\, 000$ characters, all small letters between a-z.
Output
Output a single number – the minimum number of USB HID reports that a keyboard could use to input the given text string.
| Sample Input 1 | Sample Output 1 |
|---|---|
abcdef |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
fedcba |
6 |
| Sample Input 3 | Sample Output 3 |
|---|---|
abababab |
4 |
