Uddered but not Herd

Interview

Time limit2sMemory limit512 MB

Summary

Find the fewest copies of the cowphabet needed to contain the heard string as a subsequence, where the cowphabet is a fixed reordering of a to z.

Level: Easy3 of 10
Topics: Greedy, String
Solved: No attempts yet

Problem

A little known fact about cows is that they have their own version of the alphabet, the "cowphabet". It consists of the 26 letters 'a' through 'z', but when a cow speaks the cowphabet, she lists these letters in a specific ordering that might differ from the order 'abcdefghijklmnopqrstuvwxyz' we are used to.

Bessie's cousin Mildred has been humming the cowphabet over and over again, and Farmer Nhoj is curious how many times she has hummed it.

Farmer Nhoj is not always paying attention, so he might have missed some of the letters Mildred hummed. The given string contains only the letters he remembers hearing. Compute the minimum number of times Mildred must have hummed the entire cowphabet for Farmer Nhoj to have heard the given string.

Input

The only line of input contains the lowercase string of letters that Farmer Nhoj heard Mildred say. The string has length at least $1$ and at most $10^5$ .

Output

Print the minimum number of times Mildred must have hummed the entire cowphabet.

Constraints

In test cases 1-5, Farmer Nhoj only heard letters that appear in Mildred's or Bessie's names.

In test cases 6-16, Farmer Nhoj never heard any of the letters that appear in Mildred's name.

Hint

Mildred must have hummed the cowphabet at least three times. It is possible for her to have hummed it only three times if the cowphabet starts with "mildre" and Farmer Nhoj heard the letters in uppercase as shown below.

MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyz

Examples1

Example 1
Input
```
mildredree
```
Expected output
```
3
```