Козак Вус та рядки#10252
Нещодавно Козак Вус натрапив на наступну задачу.
Є рядок . Треба знайти кількість підрядків цього рядка з такими властивостями:
Підрядок повинен мати принаймні літери;
Усі літери підрядка однакові, за виключенням однієї.
Наприклад, рядки aab, cccdc задовільняють цим властивостям, а рядки ab, ccc, aabbaa — ні.
Рядок є підрядком рядка , якщо може бути отриманим видаленням кількох (можливо, жодного або всіх) символів з початку і декількох (можливо, жодного або всіх) символів з кінця.
Допоможіть Козаку Вусу розв'язати цю задачу.
Перший рядок містить рядок (1 \le |s| \le 2 \cdot 10^5), який складається з літер латинської абетки нижнього регістру.
Виведіть єдине число — кількість підрядків з заданими умовами.
Приклад 1
Приклад 2
Приклад 3
Приклад 4
Якщо рішення працює правильно при |s| \le 100, то воно буде оцінюватися принаймні у балів.
Якщо рішення працює правильно при |s| \le 5000, то воно буде оцінюватися принаймні у балів.