Châu chấu và xâu ký tự
Đề bài
Mô tả
Cho một xâu gồm các chữ cái in hoa trong bảng chữ cái tiếng Anh.
Một con châu chấu đứng ngay trước ký tự đầu tiên của xâu (vị trí ) và muốn tới vị trí ngay sau ký tự cuối cùng (vị trí ). Trên đường đi, châu chấu chỉ được phép đứng lên những vị trí chứa nguyên âm. Trong bài này, nguyên âm gồm sáu chữ cái: A, E, I, O, U và Y.
Mỗi bước, châu chấu nhảy sang phải một khoảng bất kỳ từ đến , trong đó là khả năng nhảy của nó. Hai vị trí xuất phát và đích luôn được coi là hợp lệ để đứng, dù chúng không nằm trong xâu.
Hãy tìm giá trị nhỏ nhất của để châu chấu có thể đi từ vị trí xuất phát tới đích.
Dữ liệu vào
Một dòng duy nhất chứa xâu khác rỗng, chỉ gồm các chữ cái in hoa.
Dữ liệu ra
In ra một số nguyên duy nhất: khả năng nhảy nhỏ nhất cần thiết.
Ràng buộc
- chỉ chứa các chữ cái từ A đến Z (in hoa)
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| ABABBBACFEYUKOTT | 4 | Các nguyên âm nằm ở vị trí . Kể cả vị trí xuất phát và đích , khoảng cách lớn nhất giữa hai vị trí đứng liên tiếp là . |
| AAA | 1 | Mọi ký tự đều là nguyên âm nên châu chấu chỉ cần nhảy từng bước . |
| ABBBBBB | 7 | Chỉ có một nguyên âm ở vị trí . Từ đó châu chấu phải nhảy thẳng tới đích ở vị trí , tức là cần . |
Bình luận