Что спрашивают

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

Число подходящих подстрок может превышать предел знакового 32-битного целого. Python int хранит такой ответ точно; если какой-то буквы нет, ответ равен нулю.

Приём решения

Сгруппируем подстроки по правому концу. Для каждой позиции right запомним последние встреченные позиции всех трёх букв. Пусть их минимум равен m.

Подстрока, заканчивающаяся на right, содержит все буквы тогда и только тогда, когда её начало не правее m. Начала 0, 1, ..., m подходят, всего их m + 1. Более позднее начало отрежет последнюю доступную букву с самой ранней последней позицией.

  1. Инициализируйте последние позиции значением -1.
  2. Для очередной буквы обновите её последнюю позицию.
  3. Прибавьте min(last.values()) + 1 к ответу.

Пока хотя бы одна буква не встретилась, минимум равен -1 и вклад автоматически нулевой. Повторения не требуют отдельного условия: обновляется только последняя позиция очередной буквы.

Каждая подстрока имеет единственный правый конец и единственное начало, поэтому подсчёт не теряет кандидатов и не дублирует их. Проверка минимума трёх чисел постоянна; время — O(n), дополнительная память — O(1). Хранить множество текстов подстрок не нужно.

Разбор на примере

Ввод

PQRQP

Вывод

5
Разбор примера по шагам
Правый конецПоследние P, Q, RНовых подстрокНакоплено
00, -1, -100
10, 1, -100
20, 1, 211
30, 3, 212
44, 3, 235

До появления R подходящих подстрок нет. На позициях 2 и 3 появляется по одному допустимому началу. У последнего P минимальная из последних позиций равна 2, поэтому подходят начала 0, 1 и 2: PQRQP, QRQP и RQP. Вместе получаем пять подстрок.

Код на Python и C++

Входной алфавит содержит только P, Q, R. У каждой буквы хранится одна позиция; ответ прибавляется по всем правым концам.

В C++ ответ хранится в long long: при длине строки 106 подстрок около 5·1011, это больше предела int. Минимум трёх позиций — min({last['P'], last['Q'], last['R']}).

import sys


def solve(s):
    last = {'P': -1, 'Q': -1, 'R': -1}
    answer = 0
    for right, ch in enumerate(s):
        last[ch] = right
        answer += min(last.values()) + 1
    return answer

if __name__ == '__main__':
    print(solve(sys.stdin.readline().rstrip('\r\n')))
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
using namespace std;

long long solve(const string& s) {
    map<char, int> last = {{'P', -1}, {'Q', -1}, {'R', -1}};
    long long answer = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        last[s[right]] = right;
        answer += min({last['P'], last['Q'], last['R']}) + 1;
    }
    return answer;
}

int main() {
    string s;
    getline(cin, s);
    if (!s.empty() && s.back() == '\r')
        s.pop_back();
    cout << solve(s) << endl;
}

Типичные ошибки

  • Считать только по одному разу каждую букву

    Условие требует хотя бы одно появление. Подстрока с повторяющимися буквами тоже подходит.

  • Складывать только единицу за правый конец

    Для одного конца может подходить много начал. Добавляйте их количество, а не только признак существования окна.

  • Хранить множество текстов

    Одинаковые тексты в разных местах считаются разными подстроками. Уникализация строковых значений уменьшит ответ.

  • Использовать 32-битный счётчик

    Количество подстрок растёт квадратично с длиной строки, хотя вычисляется линейно. Для других языков нужен достаточно широкий целый тип.