Uddered but not Herd

题目描述

关于奶牛的一件鲜为人知的事实是：她们有自己版本的字母表，称为“cowphabet”。它由 26 个字母 'a' 到 'z' 组成，但当奶牛说出 cowphabet 时，她会按照某种特定顺序依次念出这些字母，这个顺序可能不同于我们习惯听到的 'abcdefghijklmnopqrstuvwxyz'。 为了打发时间，Bessie 的表亲 Mildred 一遍又一遍地哼唱 cowphabet，农夫 Nhoj 很好奇她一共哼了多少次。 给定农夫 Nhoj 听到 Mildred 说的一段只包含小写字母的字符串，计算为了让农夫 Nhoj 听到该字符串，Mildred 至少需要完整哼唱 cowphabet 多少次。农夫 Nhoj 并不总是专心听 Mildred 的哼唱，因此他可能漏听了 Mildred 哼唱的一些字母。你得到的字符串只由他记得听到的字母组成。 注意：本题每个测试用例的时间限制是默认值的两倍。

输入格式

输入只有一行，包含字符串，由农夫 Nhoj 听到 Mildred 说出的、由小写字母组成的字符串。该字符串长度至少为 $1$，至多为 $10^5$。

输出格式

输出 Mildred 必须完整哼唱 cowphabet 的最小次数。

mildredree

3

提示

Mildred 至少必须哼唱 cowphabet 三次。如果 cowphabet 以 "mildre" 开头，则 Mildred 只哼唱三次也是可能的；农夫 Nhoj 听到的字母用下方所示的大写标出。 MILDREabcfghjknopqstuvwxyz milDREabcfghjknopqstuvwxyz mildrEabcfghjknopqstuvwxyz SCORING: 在测试点 1-5 中，农夫 Nhoj 只听到了出现在 Mildred 或 Bessie 名字中的字母。 在测试点 6-16 中，农夫 Nhoj 从未听到任何出现在 Mildred 名字中的字母。 题目来源：Nick Wu 和 Brian Dean

标签: USACO|2021|Gold

来源

USACO|2021|Gold