Что спрашивают
Нужен самый длинный фрагмент, содержащий ровно 80 букв Y и не менее 90 вхождений комбинации 2025. Все четыре символа каждого учтённого вхождения должны целиком находиться в том же фрагменте.
Подходящий фрагмент существует. Ограничения различны: букв должно быть ровно заданное количество, а комбинаций может быть больше порога. Произвольные другие буквы и цифры внутри окна разрешены.
Приём решения
Будем держать самое широкое окно с не более чем 80 буквами Y для каждого правого конца. При добавлении символа справа увеличиваем счётчик Y, если нужно. Если завершилась комбинация 2025, целиком лежащая в окне, увеличиваем счётчик комбинаций.
Пока Y слишком много, сдвигаем левую границу. Перед удалением левого символа проверяем две вещи: является ли он Y и начинается ли с него полное вхождение 2025. Во втором случае уменьшаем счётчик комбинаций, потому что после сдвига их первая цифра окажется за границей окна.
- Добавьте правый символ и возможное новое полное вхождение.
- Уберите слева избыток букв Y, одновременно корректируя оба счётчика.
- Если Y ровно 80, а комбинаций не менее 90, обновите максимум длины.
Почему не надо сжимать окно из-за недостатка комбинаций? Взять более короткий фрагмент с тем же правым концом не добавит ни одной комбинации. Если в самом широком допустимом окне их мало, подходящего более короткого окна тоже нет. Если Y меньше 80, сдвиг начала также не поможет. Значит, проверять нужно только поддерживаемое окно.
Каждая граница проходит строку один раз; проверки подстроки имеют фиксированную длину четыре. Время — O(n), дополнительная память счётчиков — O(1). Полный пересчёт через window.count(...) на каждом шаге не нужен.
Разбор на примере
Получить строку ввода (Python)
print("A" + "2025" * 91 + "Y" * 81 + "B")Вывод
445
| Окно | Y | Вхождения 2025 | Длина |
|---|---|---|---|
| Вся строка | 81 | 91 | 447: слишком много Y |
| Позиции 0–444 | 80 | 91 | 445: подходит |
| Позиции 366–446 | 80 | 0 | 81: комбинаций не хватает |
Созданная строка содержит 91 повторение 2025, затем 81 букву Y, а по краям A и B. Подходит префикс до восьмидесятой Y включительно: 1 + 4 × 91 + 80 = 445. При добавлении следующей Y левая граница уйдёт за первую Y и потеряет все комбинации. Длинный суффикс с нужным числом Y не подходит без достаточного числа 2025.
Код на Python и C++
Параметры основного вызова — 80 и 90. Счётчик вхождений обновляется на обеих границах; выход первой цифры вхождения за левую границу исключает его целиком.
В C++ вхождение 2025 с позиции start проверяет s.compare(start, 4, "2025") == 0.
import sys
def solve(s, needed_y=80, needed_pattern=90):
left = ys = occurrences = best = 0
for right, ch in enumerate(s):
ys += ch == 'Y'
start = right - 3
if start >= left and s[start:right + 1] == '2025':
occurrences += 1
while ys > needed_y:
ys -= s[left] == 'Y'
if left + 3 <= right and s[left:left + 4] == '2025':
occurrences -= 1
left += 1
if ys == needed_y and occurrences >= needed_pattern:
best = max(best, right - left + 1)
return best
if __name__ == '__main__':
print(solve(sys.stdin.readline().rstrip('\r\n')))
<algorithm>
<iostream>
<string>
using namespace std;
int solve(const string& s, int needed_y = 80, int needed_pattern = 90) {
int left = 0, ys = 0, occurrences = 0, best = 0;
for (int right = 0; right < (int)s.size(); right++) {
ys += s[right] == 'Y';
int start = right - 3;
if (start >= left && s.compare(start, 4, "2025") == 0)
occurrences += 1;
while (ys > needed_y) {
ys -= s[left] == 'Y';
if (left + 3 <= right && s.compare(left, 4, "2025") == 0)
occurrences -= 1;
left += 1;
}
if (ys == needed_y && occurrences >= needed_pattern)
best = max(best, right - left + 1);
}
return best;
}
int main() {
string s;
getline(cin, s);
if (!s.empty() && s.back() == '\r')
s.pop_back();
cout << solve(s) << endl;
}
Типичные ошибки
- Требовать ровно 90 комбинаций
Для 2025 условие задаёт нижний порог. Окно с большим числом комбинаций тоже может быть ответом.
- Считать комбинации во всей строке
Оба ограничения относятся к одному окну. Комбинации за его границами не помогают выполнить условие.
- Забыть удалить ушедшее вхождение
Если левая граница прошла первую цифру комбинации, она уже не целиком внутри. При сжатии обновляйте счётчик комбинаций.
- Перебирать каждое начало отдельно
Повторное расширение окна для всех начал даёт квадратичный проход. Обе границы можно перемещать только вперёд.