Description

A little-known fact is that cows have their own writing system: “Cowlish”. Cowlish has 26 letters from 'a' to 'z', but when a cow speaks Cowlish, the alphabet order might be different from the familiar 'abcdefghijklmnopqrstuvwxyz'. Instead, she will arrange the letters in some specific order.

To pass the time, Bessie’s cousin Mildred keeps humming the Cowlish alphabet song again and again, and Farmer Nhoj is curious how many times she sang it.

Given a string of lowercase letters, which are the letters Farmer Nhoj heard Mildred sing, compute the minimum number of full Cowlish alphabet songs Mildred must have sung so that Farmer Nhoj could have heard the given string. Farmer Nhoj is not always paying attention, so he may miss some letters that Mildred sang. The given string contains only the letters he remembers hearing.

Note: For this problem, the time limit for each test case is twice the default limit.

Input Format

The input contains only one line: a string of lowercase letters, representing the letters Farmer Nhoj heard Mildred sing. The string length is at least $1$ and at most $10^5$.

Output Format

Output the minimum number of complete Cowlish alphabet songs Mildred sang.

mildredree

3

Hint

Mildred sang the alphabet song at least three times. It is possible that Mildred sang it only three times, if the Cowlish alphabet starts with "mildre", and Farmer Nhoj heard the following letters marked in uppercase.

MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyz

Test Point Properties:

• In test points 1-5, Farmer Nhoj only heard letters that appear in the names Mildred or Bessie.
• In test points 6-16, Farmer Nhoj never heard any letter that appears in Mildred’s name.

Note: This problem has only 16 test points.

Translated by ChatGPT 5