Permutation in String

Q: Какова временная сложность задачи «Перестановка в строке»?

При использовании скользящего окна сложность составляет O(m + n) , где m — длина s1 , а n — длина s2 . Вы подсчитываете s1 один раз, затем каждая буква s2 один раз входит в окно и один раз выходит из него. Повторный подсчёт каждого окна с нуля вместо этого стоит O(n · m) .

Q: Поиск перестановки в строке — это то же самое, что поиск анаграммы внутри строки?

Да. Перестановка s1 — это его анаграмма, поэтому вопрос в том, является ли какая-либо подстрока s2 длины m анаграммой s1 . При проверке двух строк целиком сравнивается количество букв; здесь то же сравнение выполняется для окна, которое перемещается по s2 .

Q: Почему здесь скользящее окно имеет фиксированный размер?

Каждая перестановка s1 содержит ровно m букв, поэтому совпадать могут только окна длины m . В задачах, таких как поиск самой длинной подстроки без повторений, окно увеличивается и уменьшается; здесь обе границы перемещаются вместе, шаг за шагом.

СреднеСкользящее окно Хеширование

+10

Перестановка строки использует те же буквы в любом порядке, каждую столько же раз, сколько в исходной строке: tar, rat и art являются перестановками друг друга. Даны две строки s1 и s2, состоящие из строчных английских букв. Верните true, если какая-либо перестановка s1 встречается в s2 как подстрока (последовательность идущих подряд символов), и false в противном случае.

Функция

checkInclusion(s1: string, s2: string) → boolean

s1string: буквы для перестановки
s2string: строка, в которой нужно выполнить поиск
Возвращаетboolean: true, если подстрока s2 является перестановкой s1

Ограничения

1 ≤ s1.length ≤ 2 × 10⁴
1 ≤ s2.length ≤ 5 × 10⁴
s1 и s2 содержат только строчные буквы английского алфавита (a — z).
s1 может быть длиннее, чем s2.

Примеры

Ввод: s1 = "tar"s2 = "smartphone"
Вывод: true
Пояснение: Подстрока art с индексами от 2 до 4 в smartphone содержит одну a, одну r и одну t — те же буквы, что и в tar.

Ввод: s1 = "noon"s2 = "onion"
Вывод: false
Пояснение: Подстроки длины 4 — это onio и nion. Для noon нужны две n и две o, а в каждом окне вместо одной из них есть i. Все буквы из noon встречаются в onion, но ни в одном окне нет нужного количества букв.

Ввод: s1 = "abcd"s2 = "dcb"
Вывод: false
Пояснение: Любая перестановка abcd состоит из 4 букв, а в dcb их всего 3, поэтому она не может содержать такую перестановку.

+17 скрытых тестов при отправке

Дополнительный вопрос

Можешь вернуть все индексы s2, с которых начинается перестановка s1, по-прежнему за время O(m + n)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Перечислять перестановки s1 бесполезно: уже 10 букв дают 3 628 800 вариантов порядка. Выход — перестать учитывать порядок. Подстрока s2 является перестановкой s1 тогда и только тогда, когда у неё такая же длина m и такое же количество каждой буквы. Поэтому каждый кандидат — это окно одной и той же фиксированной длины, и его можно сдвигать по s2, обновляя количество букв: на каждом шаге добавлять одну букву и удалять одну.

Считай каждое окно заново

Верно, но не успевает на самых больших тестах

Идея

Буквальное решение — построить все перестановки s1 и искать их — сразу отпадает: для 20 букв существует более 2 × 10^18 вариантов упорядочивания. Вместо этого рассмотрим задачу с другой стороны. Подстрока s2 является перестановкой s1, если в ней ровно m букв и каждая буква встречается столько же раз, сколько в s1. Порядок букв в ней не имеет значения.

Поэтому один раз подсчитай буквы в s1 в таблице из 26 чисел: индекс 0 соответствует a, а 25 — z. Затем возьми каждую подстроку s2 длины m, подсчитай входящие в неё буквы в новой таблице и сравни обе таблицы. Для tar в smartphone окна — это sma, mar, art и так далее; art подходит: по одной a, r и t.

Этот способ корректен, потому что проверяет каждого кандидата. Он медленный, поскольку соседние окна имеют m-1 общих букв, а ты каждый раз пересчитываешь их все. При m = 15,000 и n = 50,000 будет 35,001 окно по 15,000 букв в каждом — около 5 × 10^8 шагов.

Алгоритм

Если s1 длиннее, чем s2, верните false.
Посчитайте буквы в s1 в таблице need из 26 нулей.
Для каждого начального индекса от 0 до n-m посчитайте буквы в m символах, начиная с этого индекса, в новой таблице.
Если эта таблица совпадает с need, верните true.
После последнего окна верните false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26  # need[0] is 'a', need[25] is 'z'
    for ch in s1:
        need[ord(ch) - 97] += 1
    for start in range(n - m + 1):
        # Count the letters of s2[start : start + m] from scratch
        window = [0] * 26
        for i in range(start, start + m):
            window[ord(s2[i]) - 97] += 1
        if window == need:
            return True
    return False

Передвиньте окно и сравните количество элементов в 26

Идея

Два соседних окна отличаются всего двумя буквами. При переходе от mar к art удаляется m слева и добавляется t справа. Поэтому храните одну таблицу для текущего окна и на каждом шаге изменяйте её на +1 и -1 вместо того, чтобы снова подсчитывать m букв.

Заполните need символами из s1, а window — первыми m буквами из s2, затем сравните их. После этого для каждого i от m до n-1 добавьте s2[i], удалите s2[i-m] и снова сравните. Теперь окно — это s2[i-m+1..i], в нём по-прежнему m букв.

Каждый шаг требует двух обновлений и сравнения 26 чисел независимо от значения m. Для входных данных максимального размера это около 26 × 50,000 = 1.3 × 10^6 операций, то есть время работы линейно зависит от длины s2. Именно такое решение ожидает большинство интервьюеров.

Алгоритм

Если s1 длиннее, чем s2, верни false.
Подсчитай символы s1 в need, а первые m букв s2 — в window.
Если две таблицы равны, верни true.
Для каждого i от m до n-1: прибавь 1 для s2[i], вычти 1 для s2[i-m] и верни true, если таблицы равны.
Верни false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1  # the first window is s2[0 : m]
    if window == need:
        return True
    for i in range(m, n):
        window[ord(s2[i]) - 97] += 1      # s2[i] enters on the right
        window[ord(s2[i - m]) - 97] -= 1  # s2[i - m] leaves on the left
        if window == need:
            return True
    return False

Перемещайте окно и отслеживайте несбалансированные буквы

Идея

Сравнение 26 чисел на каждом шаге повторяет работу, потому что на шаге изменяются только два из них. Вместо этого используй одну таблицу balance: balance[c] — это количество вхождений буквы c в s1 минус количество её вхождений в окне. Окно является перестановкой s1 тогда и только тогда, когда все 26 значений баланса равны 0. Рядом с таблицей храни unbalanced — количество букв, баланс которых не равен 0, и возвращай true, как только оно достигнет 0.

В ведении учёта есть одно правило. Перед изменением balance[c], если он равен 0, баланс этой буквы изменится, поэтому увеличь unbalanced на 1. После изменения, если он равен 0, баланс этой буквы восстановился, поэтому уменьши unbalanced на 1. Буква, входящая в окно, уменьшает свой баланс на 1; буква, покидающая его, увеличивает свой баланс на 1. При переходе баланса с 2 на 1 ни одна из проверок не срабатывает, и это правильно: баланс буквы был нарушен и по-прежнему нарушен.

Проследим за строками tar и smartphone. Изначально балансы равны: a: 1, r: 1, t: 1, поэтому unbalanced равно 3. Буквы s и m входят в окно, увеличивая значение до 5, затем входит a и обнуляет свой баланс: значение становится 4. Входит r (3), а s покидает окно (2). Входит t (1), а m покидает окно (0), и окно art — это ответ.

Проверять unbalanced == 0 можно уже с первой буквы. Пока в окне меньше m букв, сумма балансов положительна, поэтому как минимум один из них не равен 0. На каждом шаге выполняется фиксированный объём работы, поэтому весь просмотр занимает O(m + n), а в таблице всегда хранится 26 чисел, то есть требуется O(1) памяти.

Алгоритм

Если s1 длиннее, чем s2, верни false.
Учти символы s1 в balance и присвой unbalanced количество букв, баланс которых не равен 0.
Для каждого индекса i строки s2 вычитай 1 из баланса символа s2[i], увеличивая unbalanced на 1, если этот баланс был равен 0, и уменьшая его на 1, если он становится равен 0.
Если i ≥ m, увеличь на 1 баланс символа s2[i-m], выполнив те же действия с учетом изменений.
Если unbalanced равен 0, верни true. После цикла верни false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    # balance[c]: copies of letter c in s1 minus copies in the window
    balance = [0] * 26
    for ch in s1:
        balance[ord(ch) - 97] += 1
    unbalanced = sum(1 for b in balance if b != 0)
    for i in range(n):
        # s2[i] enters the window on the right
        c = ord(s2[i]) - 97
        if balance[c] == 0:
            unbalanced += 1
        balance[c] -= 1
        if balance[c] == 0:
            unbalanced -= 1
        # s2[i - m] leaves on the left once the window would pass m letters
        if i >= m:
            c = ord(s2[i - m]) - 97
            if balance[c] == 0:
                unbalanced += 1
            balance[c] += 1
            if balance[c] == 0:
                unbalanced -= 1
        if unbalanced == 0:
            return True
    return False

Ловушки и крайние случаи

Большинство неправильных ответов возникает из-за ошибок на границах окна или из-за проверки того, какие буквы встречаются, а не того, сколько раз они встречаются.

Проверка только того, что каждая буква из s1 есть в окне. onio содержит все буквы из noon, но не является их перестановкой. Сравнивайте количество букв.
Удаление не той буквы. Когда s2[i] входит в окно, выходит буква s2[i-m], поэтому окно становится s2[i-m+1..i]. Удаление s2[i-m+1] оставляет окно из m-1 букв.
Пропуск первого окна. Если сравнивать только после сдвига, перестановка с индексом 0 никогда не будет найдена.
Забывание о случае, когда s1 длиннее, чем s2. В Rust выражение n - m для беззнаковых длин приводит к переполнению вниз, а в Swift диапазон 0...(n - m) вызывает сбой. Сначала верните false.
Сравнение массивов с помощью == в языке, где сравниваются ссылки. В JavaScript и Dart два разных массива никогда не равны через ==; в Java используйте Arrays.equals.

Частые вопросы4

Какова временная сложность задачи «Перестановка в строке»?

При использовании скользящего окна сложность составляет O(m + n), где m — длина s1, а n — длина s2. Вы подсчитываете s1 один раз, затем каждая буква s2 один раз входит в окно и один раз выходит из него. Повторный подсчёт каждого окна с нуля вместо этого стоит O(n · m).

Поиск перестановки в строке — это то же самое, что поиск анаграммы внутри строки?

Да. Перестановка s1 — это его анаграмма, поэтому вопрос в том, является ли какая-либо подстрока s2 длины m анаграммой s1. При проверке двух строк целиком сравнивается количество букв; здесь то же сравнение выполняется для окна, которое перемещается по s2.

Почему здесь скользящее окно имеет фиксированный размер?

Каждая перестановка s1 содержит ровно m букв, поэтому совпадать могут только окна длины m. В задачах, таких как поиск самой длинной подстроки без повторений, окно увеличивается и уменьшается; здесь обе границы перемещаются вместе, шаг за шагом.

Можно ли использовать хеш-таблицу вместо массива из 26 счётчиков?

Да, и она нужна, если строки могут содержать любые символы. Если в них только строчные буквы, массив из 26 элементов работает быстрее и использует постоянный объём памяти. При использовании карты удаляй ключ, когда его счётчик становится равен 0, чтобы карты с одинаковыми буквами считались равными, или используй счётчик unbalanced из предыдущего подхода — с картой он работает так же.

Python

def checkInclusion(s1, s2):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

s1 = "tar"
s2 = "smartphone"

Ожидается

true

Permutation in String

Функция

Ограничения

Примеры

Подсказки

Решение

Считай каждое окно заново

Передвиньте окно и сравните количество элементов в 26

Перемещайте окно и отслеживайте несбалансированные буквы

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи