Một sự thật ít người biết là bò có phiên bản bảng chữ cái riêng, gọi là "cowphabet". Nó gồm 26 chữ cái từ a đến z, nhưng khi đọc cowphabet, một con bò liệt kê các chữ cái theo một thứ tự cụ thể có thể khác thứ tự abcdefghijklmnopqrstuvwxyz quen thuộc.

Để giết thời gian, Mildred, chị em họ của Bessie, đã ngân nga cowphabet hết lần này đến lần khác, và Farmer Nhoj muốn biết cô đã ngân nga bao nhiêu lần.

Cho một xâu chữ cái thường mà Farmer Nhoj nghe Mildred đọc, hãy tính số lần ít nhất Mildred phải ngân nga toàn bộ cowphabet để ông có thể nghe được xâu đó. Farmer Nhoj không phải lúc nào cũng chú ý nên có thể đã bỏ lỡ một số chữ cái Mildred đọc. Xâu được cho chỉ gồm những chữ cái ông nhớ đã nghe thấy.

Lưu ý: Giới hạn thời gian cho mỗi test của bài này gấp đôi mức mặc định.

Dữ liệu vào

Dòng duy nhất chứa xâu chữ cái thường mà Farmer Nhoj nghe Mildred đọc. Xâu có độ dài từ \(1\) đến \(10^5\).

Dữ liệu ra

In số lần ít nhất Mildred phải ngân nga toàn bộ cowphabet.

Phân nhóm

• Trong các test 1-5, Farmer Nhoj chỉ nghe những chữ cái xuất hiện trong tên Mildred hoặc Bessie.
• Trong các test 6-16, Farmer Nhoj không nghe bất kỳ chữ cái nào xuất hiện trong tên Mildred.

Ví dụ

mildredree

3

MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyz

Nguồn

USACO 2021 January Contest, Gold - Uddered but not Herd: https://usaco.org/index.php?page=viewproblem2&cpid=1089

Tác giả: Nick Wu và Brian Dean.