A1014 | Uddered but not Herd--Gold

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 be different from the order 'abcdefghijklmnopqrstuvwxyz'
we are used to hearing.
To pass the time, Bessie's cousin Mildred has been humming the cowphabet over
and over again, and Farmer Nhoj is curious how many times she's hummed it.
Given a lowercase string of letters that Farmer Nhoj has heard Mildred say,
compute the minimum number of times Mildred must have hummed the entire
cowphabet in order for Farmer Nhoj to have heard the given string. Farmer Nhoj
isn't always paying attention to what Mildred hums, and so he might have
missed some of the letters that Mildred has hummed. The string you are told
consists of just the letters that he remembers hearing.
Note: the time limit per test case on this problem is twice the default.

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

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