Подстрока без повторов
и частотная карта

Категория

Алгоритм

Уровень

Начальный

Опирается на

Глава 10.3: схема прохода; глава 10.2: контракт и примеры; словарь Python

Зачем это знать

Задача КТП и LeetCode 3 из программы Top Interview 150

§1Условие задачи

Условие уточнено в главе 10.2, здесь оно записано в окончательном виде. В примерах главы используются строки из таблицы той же главы.

Это задача на самый длинный отрезок. Условие допустимости — «в окне нет двух одинаковых символов». Расширение окна может его нарушить, сжатие — восстановить, как с лимитом суммы в главе 10.3. Отличие в том, что по одному числу это условие не проверить.

§2Решение перебором

Прямое решение — для каждого начала l удлинять подстроку вправо, пока не встретится символ, который в ней уже есть. Символы текущей подстроки хранятся в множестве seen: проверка «есть ли символ в множестве» стоит O(1). Когда найден повтор, внутренний цикл прерывается оператором break: более длинные подстроки с тем же началом содержат тот же повтор.

def longest_unique_brute(text):
    best = 0
    for l in range(len(text)):
        seen = set()
        for r in range(l, len(text)):
            if text[r] in seen:
                break
            seen.add(text[r])
            best = max(best, r - l + 1)
    return best

Прогон на строке 'pwwkew', ответ 3. В прогоне строка передана списком символов, чтобы каждый символ стоял в своей ячейке; код работает и со строкой.

На шаге 13 найден первый повтор, и на шаге 16 множество собирается заново для начала l = 1. В этом потеря перебора: при переходе к следующему началу всё, что известно о подстроке, выбрасывается. Подстрока без повторов не длиннее числа разных символов m, поэтому внутренний цикл делает не больше m + 1 шагов, а всё решение — O(n·m). Для строки из латинских букв это немного, но в строке из миллиона разных символов Юникода m сравнимо с n, и время приближается к O(n²).

§3Частотная карта

Чтобы не собирать сведения о подстроке заново, их нужно обновлять при каждом сдвиге границы: добавлять пришедший символ и убирать ушедший. Сравнение из жизни: кладовщик ведёт карточку учёта, где для каждого товара записано, сколько штук сейчас лежит на полке. Привезли коробку — число в строке этого товара увеличилось на 1, забрали — уменьшилось на 1. Полку он при этом не пересчитывает.

>>> count = {}
>>> count.get("a", 0)
0
>>> count["a"] = count.get("a", 0) + 1
>>> count["a"] = count.get("a", 0) + 1
>>> count["b"] = count.get("b", 0) + 1
>>> count
{'a': 2, 'b': 1}
>>> count["a"] -= 1
>>> count
{'a': 1, 'b': 1}
>>> count["z"]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'z'

Теперь условие допустимости записывается через карту: окно без повторов — это окно, в карте которого все счётчики не больше 1. Проверять все счётчики на каждом шаге не нужно. До расширения окно было допустимым, в нём все счётчики равны 0 или 1. Расширение меняет один счётчик — пришедшего символа ch. Значит, нарушить условие может только он, и проверка сводится к одному сравнению: count[ch] > 1.

В таблице три задачи модуля записаны по одной схеме. Строки расширения, сжатия и условия цикла меняются вместе с состоянием окна, остальное в решениях одинаково.

§4Проход вручную

Сделайте проход сами на строке 'pwwkew'. На каждом шаге выберите, какую границу сдвинуть. Под лентой показана частотная карта окна, она меняется после каждого хода. Неверный ход не выполняется, вместо него появляется объяснение.

После прихода второй буквы w одного сжатия не хватает: сначала из окна уходит p, и повтор остаётся. Окно становится допустимым только после ухода первой w.

§5Сборка цикла и песочница

Начало функции написано: три переменные — count = {}, best = 0, l = 0. Проверки входа в этой функции нет: неверного значения у единственного параметра не бывает, пустая строка — обычный вход. Ниже восемь строк остальной части. Пришедший символ кладётся в переменную ch, чтобы не писать text[r] три раза. Расставьте строки по порядку.

Напишите функцию сами в окне ниже. Десять тестов — это восемь примеров из главы 10.2, строка с цифрами и знаками и сравнение с перебором на двухстах случайных строках. Контроль КТП требует проверить повторы и пустую строку: это тесты test_all_same, test_adjacent_repeat, test_abba и test_empty.

§6Код и пошаговый прогон

def longest_unique(text):
    count = {}
    best = 0
    l = 0
    for r in range(len(text)):
        ch = text[r]
        count[ch] = count.get(ch, 0) + 1
        while count[ch] > 1:
            count[text[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

Прогон на примере из §1. Частотная карта показана в таблице переменных, строка count. В прогоне стоит проследить за тремя местами. На шаге 18 записан ответ 3 для окна 'abc'. На шагах 22–25 в окно пришла вторая a, и одно сжатие убирает повтор. На шагах 46–52 пришла b, а первым в окне стоит a: цикл while выполняется дважды, сначала уходит a, затем b.

На шаге 47 счётчик символа a становится равным 0, и ключ остаётся в словаре. На ответ это не влияет: условие цикла читает только счётчик пришедшего символа. Ключи с нулём занимают память, но их не больше, чем разных символов в строке. При желании такой ключ удаляют строкой del count[text[l]].

Оценка времени та же, что в главах 10.3 и 10.4: каждая граница проходит строку один раз, сдвигов не больше 2·n, каждый стоит одну операцию со словарём. Память — O(m): в карте не больше ключей, чем разных символов в строке. Вызовы ниже — классы входа из контроля КТП и уточнения из главы 10.2.

>>> longest_unique("abcabcbb")
3
>>> longest_unique("bbbbb")
1
>>> longest_unique("")
0
>>> longest_unique("aA")
2
>>> longest_unique("a b a")
3

Для пустой строки цикл for не выполняется ни разу, и функция возвращает начальное значение best = 0. Отдельной проверки для этого случая в коде нет.

§7Две ошибки сжатия

Обе ошибки находятся в цикле сжатия, и обе не дают исключения: функция возвращает число больше верного. Первая — оператор if на месте while. В КТП контроль занятия требует, чтобы кандидат объяснял условие while, и этот пример показывает, что цикл нельзя заменить одной проверкой. Обе версии запущены на строке 'abba', верный ответ — 2.

Вторая ошибка — уменьшить в теле цикла счётчик пришедшего символа: count[ch] -= 1 вместо count[text[l]] -= 1. Такую строку пишут, когда рассуждают «повторяется ch, значит его счётчик и надо уменьшить». Из окна при этом уходит другой символ — тот, что стоит на левой границе. Обе версии запущены на строке 'pwwkew', верный ответ — 3.

На примере из §1, строке 'abcabcbb', вторая ошибочная версия возвращает верный ответ 3. Она ошибается, только когда уходящий символ отличается от пришедшего и ответ после этого успевает вырасти. Поэтому одного теста из условия недостаточно: в песочнице обе ошибки находят test_adjacent_repeat и сравнение с перебором, первую — ещё test_abba и test_space.

§8Вариант с позициями символов

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

def longest_unique_jump(text):
    last = {}
    best = 0
    l = 0
    for r in range(len(text)):
        ch = text[r]
        if ch in last and last[ch] >= l:
            l = last[ch] + 1
        last[ch] = r
        best = max(best, r - l + 1)
    return best

Словарь last хранит позиции всех встреченных символов, в том числе тех, что из окна уже ушли: записи при сжатии не удаляются. Поэтому в условии две проверки. Первая — символ встречался. Вторая — его прошлая позиция не левее начала окна. Если вторую проверку пропустить, левая граница может сдвинуться назад. В главе 10.2 для этого случая записан пример 'abba', верный ответ — 2.

Оба решения работают за O(n). Вариант с позициями короче на одну строку и не содержит вложенного цикла. Вариант с частотной картой следует общей схеме модуля и переносится на задачи, где символу разрешено встречаться несколько раз. На интервью подходит любой из них, если кандидат объясняет, что хранит словарь и почему левая граница не сдвигается назад.

§9Число подотрезков без повторов

В главе 10.1 процитирована задача из статьи журнала Яндекс Образования: «дан массив чисел, требуется найти число подмассивов, в которых значения всех чисел различны». Она решается той же функцией с изменением в одной строке. После цикла while окно с l по r — самый длинный отрезок без повторов с концом в r. Любой отрезок с тем же концом и началом от l до r лежит внутри него и тоже не содержит повторов. Таких начал r − l + 1. Отрезки с началом левее l содержат повтор. Значит, на каждом шаге к ответу прибавляется длина окна.

def count_unique_windows(nums):
    count = {}
    total = 0
    l = 0
    for r in range(len(nums)):
        x = nums[r]
        count[x] = count.get(x, 0) + 1
        while count[x] > 1:
            count[nums[l]] -= 1
            l += 1
        total += r - l + 1
    return total

>>> count_unique_windows([1, 2, 1, 3])
8
>>> count_unique_windows([5, 5, 5])
3
>>> count_unique_windows([1, 2, 3])
6

В списке [1, 2, 1, 3] десять подотрезков. Два из них содержат повтор единицы: [1, 2, 1] и весь список. Остаются восемь. В списке [5, 5, 5] без повторов только три отрезка из одного элемента, в списке [1, 2, 3] — все шесть. Функция сверена с перебором всех подотрезков на 5 000 случайных списков.

§10Проверьте себя