Позиции и границы

Нужен самый короткий фрагмент, в котором буква Q встречается 50 раз. С чего он начинается и чем кончается?

Он начинается на одной Q и кончается на 50-й Q, считая от неё: лишние символы по краям только удлинили бы его. Поэтому достаточно знать, где стоят все Q. Номера нужных букв собирает в список одна строка — списковое включение. Если выбраны K подряд идущих букв — в списке это элементы с j по j + K − 1, — длина фрагмента (в программе K — это k): positions[j + k - 1] - positions[j] + 1.

s = 'CAABACAB'k = 3positions = [i for i in range(len(s)) if s[i] == 'A']print(positions) best = len(s) + 1for j in range(len(positions) - k + 1):    best = min(best, positions[j + k - 1] - positions[j] + 1) print(best)

Тройки соседних A: на позициях 1, 2, 4 — фрагмент AABA длины 4, и на позициях 2, 4, 6 — длины 5. Брать A не подряд нет смысла: та, что между ними, всё равно окажется внутри. Начальное значение len(s) + 1 больше любой длины — если оно не изменилось, подходящего фрагмента нет.

А самый длинный фрагмент ровно с K буквами A? Насколько его можно растянуть?

До соседних A, не включая их: левее первой выбранной — до предыдущей A, правее последней — до следующей. Чтобы та же формула работала у краёв строки, добавим в список искусственные позиции −1 и len(s) — как будто там стоят A. Тогда длина — positions[j + k] - positions[j - 1] - 1.

s = 'BABAACB'k = 2positions = [i for i in range(len(s)) if s[i] == 'A']positions = [-1] + positions + [len(s)]best = 0for j in range(1, len(positions) - k):    best = max(best, positions[j + k] - positions[j - 1] - 1) print(positions, best)

Первые две A растягиваются от начала строки до позиции 3 — BABA, длина 4. Последние две — от позиции 2 до конца строки: BAACB, длина 5.

Это тот же ответ, что дало скользящее окно в подтеме 4. Позиции удобнее, когда K большое, а нужные буквы редкие: цикл идёт по списку, а не по всей строке.

Самый короткий фрагмент с двумя вхождениями слова ABA — как его найти, если вхождения могут перекрываться?

Так же, по списку позиций, только теперь это начала слова. Последнее слово кончается на m − 1 символов дальше своего начала, поэтому длина — starts[j + k - 1] - starts[j] + m. Начала ищем перебором, как в подтеме 3, — перекрытия не теряются.

s = 'ABACABABA'word = 'ABA'm = len(word)starts = [i for i in range(len(s) - m + 1) if s[i:i + m] == word]best = len(s) + 1for j in range(len(starts) - 1):    best = min(best, starts[j + 1] - starts[j] + m) print(starts, best)

Вхождения с позиций 4 и 6 перекрываются, вместе это ABABA — 5 символов, а не 6. Та же формула работает для пар вроде TT: m = 2.

Фрагмент начинается и заканчивается одной и той же цифрой, а внутри только буквы. Где искать его концы?

Только среди соседних цифр строки: если между концами окажется ещё одна цифра, внутри будут уже не только буквы. Значит, перебираем пары соседних позиций цифр. s[i].isdigit() проверяет, что символ — цифра.

s = '5BA57OK7TEX2KA9'digits = [i for i in range(len(s)) if s[i].isdigit()]best = 0for j in range(len(digits) - 1):    a, b = digits[j], digits[j + 1]    if s[a] == s[b]:        best = max(best, b - a + 1) print(digits, best)

Подходят 5BA5 и 7OK7, обе длины 4. Пара 2…9 — разные цифры. Так решаются многие задачи с особыми концами: сначала выписать, где могут стоять концы, потом проверить пары — это гораздо меньше, чем перебор всех фрагментов.

Похоже устроено условие «фрагмент без цифр, в котором есть все шесть гласных»: цифры делят строку на блоки букв, и для максимума выгодно брать блок целиком. Проверка — set('AEIOUY') <= set(block): все гласные есть среди букв блока.

• Самый короткий с Kpositions[j + k - 1] - positions[j] + 1
• Самый длинный ровно с Kpositions[j + k] - positions[j - 1] - 1
• Искусственные границы−1 и len(s) в начале и в конце списка
• Слово длины mпоследнее начало − первое + m
• Особые концыконцы — среди позиций особых символов, перебор пар