Подстроки с тремя буквами
Время 2 с · память 256 МБ
Строка состоит из заглавных букв латинского алфавита P, Q и R. Определите количество её подстрок — последовательностей идущих подряд символов, — в каждой из которых все три буквы встречаются хотя бы по одному разу.
Подстроки, которые начинаются или заканчиваются в разных местах строки, считаются различными, даже если состоят из одинаковых символов.
Входные данные
Во входных данных содержится одна непустая строка длиной не более символов.
Выходные данные
Выведите одно число — количество таких подстрок. Оно может быть больше .
Примеры
Ввод 1
PQRRP
Вывод 1
4
Ввод 2
PPQQ
Вывод 2
0
Примечание
В первом примере таких подстрок четыре: PQR, PQRR, PQRRP и QRRP.
Во втором примере строка PPQQ не содержит буквы R, поэтому подстрок со всеми тремя буквами нет. Их количество равно 0.