Алгоритмические задачи со строками – Учебник

8.3

О чём этот урок

У строки есть готовый метод почти на любой вопрос. Найти кусок – find(), заменить – replace(), разрезать по разделителю – split(), снять пробелы по краям – strip(). Пока вопрос звучит как «где», «сколько раз» или «на что заменить», ответ за нас уже написан.

Но стоит спросить иначе – «какая цепочка самая длинная», «сколько одинаковых символов идёт подряд», «есть ли кусок, в котором ровно k таких букв», – и готового метода не находится. Общее у таких вопросов одно: ответ зависит не от всей строки разом, а от куска строки, а кусков в строке много и годятся из них не все. Язык не знает, какой кусок нужен вам, – и строку приходится проходить самому.

В этом уроке: общий приём, на котором держатся все такие задачи, – один проход по строке и переменные-накопители; самая длинная цепочка одинаковых символов подряд; проверка строки на палиндром двумя способами – срезом и двумя указателями; поиск самого короткого отрезка с заданным числом нужных букв, где впервые появляется приём «окно». Нового инструмента не будет ни одного: всё уже в руках – индекс, срез, in, count(), lower(), isalpha() и обычный цикл.

Общий приём: один проход и накопитель

Задачи этого урока решаются не озарением, а одной общей схемой:

нормализовать – привести строку к виду, в котором сравнение честное (регистр, лишние символы);
пройти один раз слева направо;
накопить ответ в переменных, которые живут между шагами цикла.

Переменные-накопители – та же идея, что в поиске минимума и максимума (блок 4): не хранить все увиденные значения, а держать одно, самое нужное, и обновлять его по дороге. Здесь вместо чисел – символы и их счётчики. Это и есть память программы о том, что она уже видела.

Почему «один проход», а не «пройти столько раз, сколько понадобится»? Потому что строка неизменяема: лишний проход – это лишняя работа, символы придётся перечитывать с самого начала. Всё, что понадобится в конце, надо копить по дороге.

И сразу честное предупреждение: почти вся сложность таких задач не в основной идее, а в краях – первом символе, последнем символе и пустой строке. Идею придумывают за минуту, а ломается решение всегда там.

Задача 1. Самая длинная цепочка одинаковых символов

Постановка: дана строка, надо найти длину самой длинной группы одинаковых символов, идущих подряд. В 'ААБВВВВГ' ответ 4 (четыре «В»), в 'абвгд' – 1, в пустой строке – 0.

Идея. Идём по строке начиная со второго символа и на каждом шаге задаём один вопрос: «этот символ такой же, как предыдущий?»

да – текущая цепочка продолжается, её длина растёт на 1;
нет – цепочка оборвалась, начинается новая, и в ней пока один символ.

Отсюда две переменные:

cur – длина цепочки, которая идёт прямо сейчас;
best – самая длинная из всех, что уже встретились.

Правило, которое стоит запомнить дословно: сначала обнови cur, а потом сразу сверь его с best – на каждом шаге, а не в момент обрыва цепочки. Почему именно так, разберём чуть ниже: это главная ловушка задачи.

Сравнение соседей – это s[i] == s[i - 1], и здесь работает ровно то, что дал урок 8.1: символ достаётся по индексу, строку при этом никто не меняет.

Строка разбита на цепочки одинаковых символов. `cur` растёт внутри цепочки и сбрасывается в 1 на её границе, а `best` запоминает лучшее из уже увиденного и никогда не уменьшается.

s = 'ААБВВВВГ'

best = 0                   # ответ для пустой строки уже готов
cur = 0
if len(s) > 0:
    best = 1               # первый символ – цепочка длиной 1
    cur = 1

for i in range(1, len(s)):  # со второго символа: у первого нет
    if s[i] == s[i - 1]:    # предыдущего, сравнивать не с чем
        cur = cur + 1      # цепочка продолжается
    else:
        cur = 1            # началась новая, в ней один символ
    if cur > best:         # сверяем на каждом шаге, а не
        best = cur         # в момент обрыва цепочки

print(best)                # 4

# та же программа на других строках:
#   'абвгд'   -> 1   ни одна пара соседей не совпала
#   'ААБВВВВ' -> 4   цепочка упирается в конец строки
#   ''        -> 0   цикл не выполнился ни разу

Три края, на которых решение ломается

Идея заняла абзац, а вот три места, где её легко испортить.

1. Последняя цепочка. Соблазн – обновлять best в момент обрыва цепочки: «кончилась – подвели итог». На 'ААБВВВВГ' это ещё сработает, а на 'ААБВВВВ' – нет: последняя цепочка ничем не обрывается, строка просто кончается, и итог по ней никто не подведёт. Программа ответит 2 вместо 4. Лечение – сверять на каждом шаге, тогда особого случая «конец строки» просто не существует.

2. Первый символ. У него нет предыдущего. И s[i - 1] при i = 0 даст не ошибку, а последний символ строки – отрицательный индекс из урока 8.1 сработает молча и испортит ответ: на строке 'АБА' программа решит, что первая и «предыдущая» буквы совпали. Поэтому цикл начинается с 1, а первый символ учтён заранее как цепочка длиной 1.

3. Пустая строка. Цикл не выполнится ни разу, и best останется тем, чем его назначили. Напишешь best = 1 без проверки – программа сообщит о цепочке в строке, где нет ни одного символа.

Общая мораль, которая пригодится и дальше: краевые случаи – не редкая экзотика, а обязательная часть проверки. Три вопроса к любой готовой программе: что будет на пустом входе, что на входе из одного элемента и что, если ответ лежит в самом конце.

Задача 2. Палиндром

Палиндром – текст, который читается одинаково слева направо и справа налево.

Со словом 'шалаш' всё просто. С «А роза упала на лапу Азора» – нет: там пробелы и две заглавные буквы. Для человека это не помеха, а для программы 'А' == 'а' – ложь: это два разных символа с разными кодовыми точками (уроки 8.1 и 8.2).

Поэтому решение делится на два независимых шага, и путать их не надо:

нормализация – оставить только буквы и привести их к одному регистру;
проверка – сравнить получившееся с самим собой наоборот.

Первый шаг – ровно тот цикл, что собирал очищенную строку в уроке 8.2: идём по символам, спрашиваем у каждого isalpha(), подходящие приклеиваем в нижнем регистре к новой строке. Второй шаг после этого – одно сравнение:

clean == clean[::-1]

Срез [::-1] разворачивает строку целиком, а палиндром от не-палиндрома отличает ровно то, что перевёрнутая строка равна исходной. Длина при развороте не меняется, так что сравнение всегда честное. Края разбираются сами собой: пустая строка и строка из одного символа – палиндромы, потому что переворачивать в них нечего.

И честная оговорка. В уроке 8.2 сказано, что собирать строку в цикле склейкой не надо и правильный инструмент – join(). Это по-прежнему правда, но чтобы отдать join() куски, нужен список и метод append(), а списками мы займёмся в блоке 9. Так что сейчас собираем склейкой – сознательно и понимая, что это не окончательный вариант.

Второй способ – два указателя. Разумный вопрос: если одной строки хватает, зачем что-то ещё? Затем, что срез [::-1] строит новую строку целиком – копию всей исходной, до последнего символа, – и только потом сравнивает. Человек, проверяя палиндром глазами, так не делает: он берёт первую и последнюю буквы, сравнивает и останавливается на первом же несовпадении. У слова 'арбуз' первая буква «а», последняя «з» – ответ известен после одного сравнения, остальные буквы можно не смотреть.

Приём называется два указателя: переменная i идёт слева направо, j – справа налево, работа продолжается, пока i < j. Как только s[i] != s[j], ответ False и break; если указатели встретились – все пары совпали, ответ True. Сравнений выходит вдвое меньше, чем символов в строке, а на нечётной длине центральный символ не проверяется вообще – сравнивать его не с чем.

Ответ у обоих способов один и тот же, различаются они ценой: один строит копию всей строки, второй обходится двумя переменными. Что писать в реальной программе – обычно первый, он короче и читается мгновенно; второй важен как приём, и «двумя концами навстречу» мы ещё вернёмся, когда дойдём до списков и сортировок.

text = 'А роза упала на лапу Азора'

clean = ''
for c in text:
    if c.isalpha():            # знаки и пробелы отбрасываем
        clean = clean + c.lower()

print(clean)                   # арозаупаланалапуазора
print(clean[::-1])             # арозаупаланалапуазора – та же строка
print(clean == clean[::-1])    # True

print('привет' == 'привет'[::-1])   # False – тевирп это не привет

print('' == ''[::-1])          # True – переворачивать нечего
print('я' == 'я'[::-1])        # True – и в строке из одного символа тоже

Задача 3. Отрезок с заданным свойством

Постановка. Дана строка из букв и число k. Нужно найти минимальную длину непрерывного куска, внутри которого буква X встречается ровно k раз.

В строке 'AXBXCX' буква X стоит на позициях 1, 3 и 5. При k = 2 подойдёт кусок 'XBX' длиной 3; кусок 'AXBXC' тоже содержит две X, но он длиннее. Если букв X в строке меньше, чем k, подходящего куска нет вовсе.

Перебрать все пары границ – начало куска и конец – можно, но пар слишком много: на строке в миллион символов такой перебор не досчитает.

Идея окна. Держим не пару границ, а окно – кусок между левой и правой границей, – и обе двигаем только вперёд. Правую двигаем шаг за шагом, пока внутри не наберётся ровно k букв X. Как только набралось – подтягиваем левую, пока букв внутри всё ещё k, и запоминаем длину. Выбрасывать стало нечего – снова двигаем правую.

s = 'AXBXCX'
k = 2                   # сколько букв X должно быть внутри куска

left = 0                # левая граница окна
count = 0               # сколько X внутри окна прямо сейчас
best = -1               # длина самого короткого подходящего куска

for right in range(len(s)):
    if s[right] == 'X':
        count = count + 1

    # справа набралось ровно k букв X – окно можно подтягивать
    while count == k:
        length = right - left + 1
        if best == -1 or length < best:
            best = length       # запомнили, пока окно подходит
        if s[left] == 'X':
            count = count - 1   # отпустили X: внутри осталось k - 1
        left = left + 1         # левая граница шагнула вправо

print(best)             # 3 – самый короткий кусок 'XBX'

# та же программа на других строках:
#   'XXABX', k = 2  ->  2   кусок 'XX'
#   'AXB',   k = 2  -> -1   двух X в строке нет

Почему окно вообще работает

Левую границу никогда не приходится возвращать назад. Пока внутри меньше k букв X, окно может расти только справа. Как только их ровно k, левую двигают вперёд – символы, которые из окна ушли, ответ короче уже не сделают.

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

Что общего у трёх решений

Три разные задачи – одна схема:

Задача	Нормализация	Что копим по дороге	Ответ
Цепочка	не нужна	`cur` и `best`	значение `best`
Палиндром	только буквы, нижний регистр	ничего – сравниваем целиком или парами	сошлись ли все пары
Отрезок	не нужна	`left`, `count` и `best`	значение `best`

Третья задача устроена иначе, и это стоит заметить. В цепочке и палиндроме накопитель отвечал на вопрос «что уже было»; в задаче про отрезок копится ещё и место, до которого просмотрена строка, – левая граница. Именно она и делает окно окном: без неё пришлось бы возвращаться назад, а возвращаться по строке назад – это ровно тот перебор всех пар границ, от которого мы уходили.

Общее у всех трёх – не приём, а порядок работы. Когда готового метода нет, задача решается не озарением, а разбором на три вопроса: что надо привести к общему виду перед сравнением, что нужно помнить между шагами цикла и на чём решение сломается по краям. Все три ответа собираются из инструментов, которые уже есть.

Коротко

Готового метода у задач этого урока нет, но и нового инструмента не нужно: всё решается индексом, срезом, count(), lower() и обычным циклом.
Общая схема: нормализовать – пройти один раз – накопить ответ. Накопитель – это память программы между шагами цикла: строка неизменяема, перечитать её заново дёшево не выйдет.
Самая длинная цепочка: cur живёт внутри текущей серии, best – над всей строкой. Сверять их надо на каждом шаге, а не в момент обрыва, иначе цепочка, упёршаяся в конец строки, потеряется. Первый символ учитывается отдельно, пустая строка даёт 0.
Палиндром делится на два независимых шага: нормализация (только буквы, один регистр) и проверка. Проверка – либо clean == clean[::-1] (коротко, но строит копию строки), либо два указателя навстречу (сравнений вдвое меньше, останавливаются на первом несовпадении).
Отрезок с заданным числом букв X ищется окном: правая граница расширяет окно, левая подтягивает его, когда внутри стало ровно k. Обе границы идут только вперёд – по строке не приходится возвращаться.
Любое готовое решение проверяют на краях: пустая строка, строка из одного символа и ответ, который лежит в самом конце.