Статья Автор: Лебедев Дмитрий Алексеевич

2025_Декабрыь разбор

Подход к решению одного из типов задания 24.
Обобщенная формулировка задачи.

Есть последовательность элементов/символов.
Определено понятие слова, причем слова могут "пересекаться", но не совпадать
Необходимо найти длину наименьшей/наибольшей подпоследовательности, содержащей
заданное количество слов (ровно/не более/не менее)

Способ решения состоит в следующем

Определить "индексы окончания" для всех слов (и их количество N_R).
Индексы записать и I_R - словарь/список (ключ номер слова)
Решение с помощью обычного цикла по строке!!!
Аналогично для "индексов начала", получить N_L и I_L
Вывести/сравнить N_R и N_L - они должны "совпадать" (при условии, что "индекс начала" первого слова меньше "индекса Финала" первого слова и аналогично для последних слов)
Это определенная проверка правильности решения пунктов 1,2
В цикле по i от 1 до N_L выполняем :
- находим j - номер "финального" слова (i + k - 1), где k - требуемое количество слов
- если j-е слово "ЕСТЬ", то находим длину последовательности и обрабатываем её

Достоинства подхода

Задача разбивается на несколько "технических" этапов, резализуемых с помощью циклов
Для каждого этапа возможна "простая независимая проверка"
Есть дополнительная проверка по количеству индексов "Начало слова", "Финал слова"

Недостатки

два прохода по последовательносит (1 и 2 этап можно объединить)
желательно "посмотреть" начало и окончание последовательности, чтобы оценить начало/окончание последовательности перебора для 1-2 этапов (или придется автоматизировать этот процесс)
использование дополнительной памяти для хранение индексов, но если понимать, что можно обойтись без хранение всей строки, то этот аргумент теряет актуальность

Практически, реализован метод "двух указателей", разделенный на пару проходов.
Назовем такой способ "упрощенным методом двух указателей"
Для демонстрации способа, разберем поэтапное решение задачи из Статграда (декабрь 2025 года)

Условие задания:

68613

# Реализация подготовительного этапа
# Чтение строки, вывод Длины, Начала, Окончания
ss = open('24_25-12.txt').readline()
print(f'{len(ss)=}\n{ss[:10]=}\n{ss[-10:]=}')

Анализ Начала и Окончания строки показывает, что окончание слова можно искать на всей длине строки.
Осуществим 1 этап - получение "индексов окончания"
"Финал слова" - это "первая буква" после "цифры"

Зададим строку цифр (чтобы не вспоминать методы строк) /Лучше множество, но это "долго"
Буква - это "Не цифра" (в условиях задачи)
Финал слова - это буква, перед которой цифра

ss = open('24_25-12.txt').readline()
print(f'{len(ss)=} {ss[:10]=} {ss[-10:]=}')  
# 1 этап
dd = "0123456789"
Nr = 0
Ir ={}
for i in range(1, len(ss)):
  if (not (ss[i] in dd)) and (ss[i-1] in dd) :
    Nr += 1
    Ir[Nr] = i
print(Nr)

Реализуем блок 2
"Скопируем" блок 1 и немного подправим

изменим границы прсмотра
изменим правило для определения свершившегося события,
понимая, что "Начало слова" - это "последняя буква" перед цифрой

ss = open('24_25-12.txt').readline()
print(f'{len(ss)=} {ss[:10]=} {ss[-10:]=}')  
# 1 этап
dd = "0123456789"
Nr = 0
Ir ={}
for i in range(1, len(ss)):
  if (not (ss[i] in dd)) and (ss[i-1] in dd) :
    Nr += 1
    Ir[Nr] = i
print(Nr)    
Nl = 0
Il = {}
for i in range(len(ss) - 1):
  if (not(ss[i] in dd)) and (ss[i+1] in dd) :
    Nl += 1
    Il[Nl] = i
print(Nl)

Реализуем 3 и 4 блоки
Блок 3 - это визуальное сравнение количества индексов
Блок 4 - цикл по индексам Начал (делаем даже без break)

находим индекс "финального" слова
если "финальное" существует, то
- находим длину подпоследовательности
- обрабатываем ответ

ss = open('24_25-12.txt').readline()
print(f'{len(ss)=} {ss[:10]=} {ss[-10:]=}')  
# 1 этап
dd = "0123456789"
Nr = 0
Ir ={}
for i in range(1, len(ss)):
  if (not (ss[i] in dd)) and (ss[i-1] in dd) :
    Nr += 1
    Ir[Nr] = i
print(Nr)    
Nl = 0
Il = {}
for i in range(len(ss) - 1):
  if (not(ss[i] in dd)) and (ss[i+1] in dd) :
    Nl += 1
    Il[Nl] = i
print(Nl)   
kk = 10000
ans = len(ss)
for i in range (1, Nl) :
  j = i + kk -1
  if j in Ir :
    if Ir[j] - Il[i] + 1 < ans :
      ans = Ir[j] - Il[i] + 1
print(ans)

Подведем итоги
Попробуем понять, насколько целесообразно было бы использовать множество символов вместо строки "0123456789"

ss = open('24_25-12.txt').readline()
print(f'{len(ss)=} {ss[:10]=} {ss[-10:]=}')  
# 1 этап
dd = {'0','1','2','3','4','5','6','7','8','9'}
Nr = 0
Ir ={}
for i in range(1, len(ss)):
  if (not (ss[i] in dd)) and (ss[i-1] in dd) :
    Nr += 1
    Ir[Nr] = i
print(Nr)    
Nl = 0
Il = {}
for i in range(len(ss) - 1):
  if (not(ss[i] in dd)) and (ss[i+1] in dd) :
    Nl += 1
    Il[Nl] = i
print(Nl)   
kk = 10000
ans = len(ss)
for i in range (1, Nl) :
  j = i + kk -1
  if j in Ir :
    if Ir[j] - Il[i] + 1 < ans :
      ans = Ir[j] - Il[i] + 1
print(ans)

Прикрепленные файлы
24_25-12.txt

Печать