레이팅 미적용소에 관한 잘 알려지지 않은 사실 하나는, 소들에게는 그들만의 알파벳인 "소 알파벳(cowphabet)"이 있다는 것이다. 소 알파벳은 'a'부터 'z'까지 26개의 문자로 이루어져 있지만, 소가 소 알파벳을 말할 때는 우리가 익숙하게 듣는 'abcdefghijklmnopqrstuvwxyz' 순서와 다를 수 있는 특정한 순서로 문자들을 나열한다.
시간을 보내기 위해 베시의 사촌 밀드레드는 소 알파벳을 계속해서 반복해 흥얼거리고 있는데, 농부 뇌즈(Nhoj)는 밀드레드가 그것을 몇 번이나 흥얼거렸는지 궁금하다.
농부 뇌즈가 밀드레드에게서 들은 소문자 문자열이 주어질 때, 농부 뇌즈가 주어진 문자열을 듣기 위해 밀드레드가 소 알파벳 전체를 흥얼거려야 했던 최소 횟수를 계산하시오. 농부 뇌즈는 밀드레드가 흥얼거리는 것에 항상 집중하고 있지는 않아서, 밀드레드가 흥얼거린 문자 중 일부를 놓쳤을 수 있다. 주어지는 문자열은 그가 들었다고 기억하는 문자들만으로 이루어져 있다.
참고: 이 문제의 테스트 케이스당 시간 제한은 기본값의 두 배이다.
문제 제공: Nick Wu, Brian Dean
배점
- 테스트 케이스 1-5에서는 농부 뇌즈가 Mildred나 Bessie의 이름에 나타나는 문자만 들었다.
- 테스트 케이스 6-16에서는 농부 뇌즈가 Mildred의 이름에 나타나는 문자를 하나도 듣지 않았다.
문제 제공: Nick Wu, Brian Dean
입력은 한 줄로, 농부 뇌즈가 밀드레드에게서 들은 소문자 문자열이 주어진다. 이 문자열의 길이는 최소 \(1\), 최대 \(10^5\)이다.
밀드레드가 소 알파벳 전체를 흥얼거려야 했던 최소 횟수를 출력한다.
mildredree3Mildred must have hummed the cowphabet at least three times. It is possible for
Mildred to have only hummed the cowphabet three times if the cowphabet starts
with "mildre" and Farmer Nhoj heard the letters in uppercase as denoted below.
MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyz