Uddered but not Herd (Gold)#11201
A little-known fact about cows is that they have their own version of the alphabet, called the cowphabet. It consists of the letters '' through '', but when a cow recites the cowphabet, she lists the letters in a specific order, which may differ from the usual order 'abcdefghijklmnopqrstuvwxyz'.
To pass the time, Bessie's cousin Mildred hums the cowphabet repeatedly, and Farmer Nhoj wonders how many times she has hummed it.
Given a string of lowercase letters that Farmer Nhoj heard Mildred say, determine the minimum number of times Mildred must have hummed the entire cowphabet for Farmer Nhoj to have heard the given string. Farmer Nhoj is not always paying attention, so he may have missed some of the letters Mildred hummed. The given string contains only the letters that he remembers hearing.
The only line of input contains a string of lowercase letters that Farmer Nhoj heard Mildred say. The length of the string is between and 10^5, inclusive.
Print the minimum number of times Mildred must have hummed the entire cowphabet.
Mildred must have hummed the cowphabet at least three times. It is possible for her to have hummed the cowphabet exactly three times if the cowphabet begins with "mildre". The letters Farmer Nhoj heard are shown in uppercase below:
MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyzExample 1