Задача 13 из 14

Подстроки с тремя буквами

Время 2 с · память 256 МБ

Строка состоит из заглавных букв латинского алфавита P, Q и R. Определите количество её подстрок — последовательностей идущих подряд символов, — в каждой из которых все три буквы встречаются хотя бы по одному разу.

Подстроки, которые начинаются или заканчиваются в разных местах строки, считаются различными, даже если состоят из одинаковых символов.

Входные данные

Во входных данных содержится одна непустая строка длиной не более 10610^6 символов.

Выходные данные

Выведите одно число — количество таких подстрок. Оно может быть больше 2312^{31}.

Примеры

Ввод 1
PQRRP
Вывод 1
4
Ввод 2
PPQQ
Вывод 2
0

Примечание

В первом примере таких подстрок четыре: PQR, PQRR, PQRRP и QRRP.

Во втором примере строка PPQQ не содержит буквы R, поэтому подстрок со всеми тремя буквами нет. Их количество равно 0.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче