Алфавітна послідовність
Обмеження: 2 сек., 512 МіБ
Зеник з Марічкою мають ферму з n жеребцями. Коні на фермі мають різні масті — вороні, гніді, булані та інші. Усього бувають 26 різних мастей, позначених малими латинськими буквами.
Фермери вишикували своїх жеребців у шеренгу. Шеренгу можна подати рядком s з n малих букв англійського алфавіту, що позначають масті коней у шерензі.
Назвемо послідовність коней алфавітною, якщо одночасно виконуються такі дві умови:
усі масті коней у послідовності різні,
букви, що позначають масті коней, виписані в порядку послідовності, ідуть в алфавітному порядку.
Наприклад, послідовності abx, qrtu,
m є алфавітними, а послідовності aab,
qwerty — ні.
Вам потрібно знайти розмір найдовшого проміжку заданої шеренги жеребців, який є алфавітною послідовністю.
Вхідні дані
У першому рядку задано ціле число n — кількість жеребців у шерензі.
У другому рядку задано рядок s з n малих латинських букв, що позначає шеренгу коней.
Вихідні дані
Виведіть одне ціле число — розмір найдовшого проміжку заданої шеренги жеребців, який є алфавітною послідовністю.
Обмеження
1≤n≤2⋅105.
Оцінювання складається з таких блоків:
по 1 балу за кожен приклад з умови,
5 балів: s складається лише із символів
a,11 балів: s складається лише із символів
a,b,16 балів: s складається лише із символів
a,b,c,14 балів: n≤100,
19 балів: n≤5000,
33 бали: без додаткових обмежень.
Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 8 olympiad | 2 |
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 10 algotester | 3 |
Примітки
У першому прикладі s=
olympiad. У цій шерензі є декілька проміжків довжини 2, які є алфавітними послідовностями:
ly, mp, ad. Жодного такого
проміжка довжини більшої за 2
немає. Тому відповідь дорівнює 2.
У другому прикладі s=
algotester. Тут є проміжки довжиною 3, які є алфавітними послідовностями:
got, est.