eolymp
Competitions

Ukrainian Olympiad in Informatics, II Stage, I Round

G. Козак Вус та рядки

Нещодавно Козак Вус натрапив на наступну задачу. Є рядок $s$. Треба знайти кількість підрядків цього рядка з такими властивостями: \begin{enumerate} \item Підрядок повинен мати принаймні $3$ літери; \item Усі літери підрядка однакові, за виключенням однієї. \end{enumerate} Наприклад, рядки \t{aab}, \t{cccdc} задовільняють цим властивостям, а рядки \t{ab}, \t{ccc}, \t{aabbaa} --- ні. Рядок $x$ є підрядком рядка $y$, якщо $x$ може бути отриманим видаленням кількох (можливо, жодного або всіх) символів з початку і декількох (можливо, жодного або всіх) символів з кінця. Допоможіть Козаку Вусу розв'язувати цю задачу. \InputFile Перший рядок містить рядок $s$ ($1 \le |s| \le 2 \cdot 10^5$), який складається з літер латинської абетки нижнього регістру. \OutputFile Виведіть єдине число --- кількість підрядків з заданими умовами. \Scoring Якщо рішення працює правильно при $|s| \le 100$, то воно буде оцінюватися принаймні у $15$ балів. Якщо рішення працює правильно при $|s| \le 5000$, то воно буде оцінюватися принаймні у $40$ балів.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
abcbb
Output example #1
3
Input example #2
abacabadabacaba
Output example #2
7
Input example #3
hello
Output example #3
2
Input example #4
yyyyxyyyzttt
Output example #4
21
Source Ukrainian Olympiad in Informatics 2021, II Stage, I Round