(Даня Байт) Текстовый файл состоит из цифр 0–9 и букв A–Z. Определите в прилагаемом файле длину самой длинной непрерывной подпоследовательности, которая состоит только из цифр и содержит не более 3 различных цифр.
Для выполнения этого задания следует написать программу.
Решение
Скользящее окно
🔹 Шаг 1. Читаем файл в строку s
s = open("24.txt").read()
ans = 0
l = 0
cnt = {}
📌 Читаем файл в строку s. Задаём ans для ответа, левую границу l скользящего окна и словарь cnt — сколько раз каждая цифра встречается в текущем окне.
🔹 Шаг 2. Перебираем символы индексом r
for r in range(len(s)):
if not s[r].isdigit():
l = r + 1
cnt.clear()
continue
📌 Перебираем символы индексом r. Если символ не цифра — цепочка цифр прервалась: сбрасываем окно, ставим l = r + 1 и очищаем cnt.
🔹 Шаг 3. Добавляем цифру s[r] в окно
cnt[s[r]] = cnt.get(s[r], 0) + 1
📌 Добавляем цифру s[r] в окно: увеличиваем её счётчик в cnt.
🔹 Шаг 4. Пока в окне больше трёх различных цифр, сдвигаем l вправо и уменьшаем…
while len(cnt) > 3:
cnt[s[l]] -= 1
if cnt[s[l]] == 0:
del cnt[s[l]]
l += 1
📌 Пока в окне больше трёх различных цифр, сдвигаем l вправо и уменьшаем счётчики цифр, которые выходят из окна. Затем обновляем ans длиной r − l + 1.
🔹 Шаг 5. Жми RUN
ans = max(ans, r - l + 1)
print(ans)
📌 Жми RUN — в выводе будет 14 (максимальная длина подходящей подпоследовательности).
✅ Ответ: 14
🔹 Полный код
s = open("24.txt").read()
ans = 0
l = 0
cnt = {}
for r in range(len(s)):
if not s[r].isdigit():
l = r + 1
cnt.clear()
continue
cnt[s[r]] = cnt.get(s[r], 0) + 1
while len(cnt) > 3:
cnt[s[l]] -= 1
if cnt[s[l]] == 0:
del cnt[s[l]]
l += 1
ans = max(ans, r - l + 1)
print(ans)