Longest Palindromic Substring

СреднеДва указателя Динамическое программирование

+10

Тебе дана строка s, состоящая из строчных английских букв. Верни её самую длинную палиндромную подстроку: самую длинную последовательность идущих подряд букв, которая одинаково читается слева направо и справа налево. Если несколько подстрок имеют одинаковую максимальную длину, верни ту, которая начинается левее остальных.

Функция

longestPalindrome(s: string) → string

sstring: строка в нижнем регистре для поиска
Возвращаетstring: самая длинная палиндромная подстрока s, самая левая из них, если несколько имеют одинаковую длину

Ограничения

1 ≤ s.length ≤ 2000
s содержит только строчные буквы английского алфавита.
Если несколько палиндромов имеют максимальную длину, ответом будет тот, у которого наименьший начальный индекс.

Примеры

Ввод: s = "bananas"
Вывод: "anana"
Пояснение: "anana" одинаково читается с обоих концов и состоит из 5 букв. Более длинные фрагменты не подходят: "banana" начинается с b и заканчивается на a, "ananas" начинается с a и заканчивается на s, а всё слово начинается с b и заканчивается на s.

Ввод: s = "xyzzyabba"
Вывод: "yzzy"
Пояснение: "yzzy" и "abba" — палиндромы длины 4, и более длинных не существует. "yzzy" начинается с индекса 1, раньше "abba" с индекса 5, поэтому при равенстве выигрывает он.

Ввод: s = "abcd"
Вывод: "a"
Пояснение: Никакие две буквы не равны, поэтому каждый палиндром состоит из одной буквы. Самый левый из них — "a".

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

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

Сможешь найти ответ за время O(n)?

Подсказки

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

Открыто 0 из 3

Решение

Палиндром зеркально симметричен относительно середины, и эта середина — либо одна буква (нечётная длина, как у "anana"), либо промежуток между двумя одинаковыми буквами (чётная длина, как у "abba"). Проверка каждой подстроки по отдельности не учитывает эту структуру и требует O(n³). Расширение каждого палиндрома от середины наружу позволяет повторно использовать результаты сравнений и сокращает время поиска до O(n²) при использовании O(1) дополнительной памяти.

Проверь каждую подстроку

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

Идея

Подстрока определяется первым индексом i и последним индексом j. Проверьте её двумя указателями: сравните s[i] с s[j], затем s[i+1] с s[j-1] и так далее, остановившись при первом несовпадении. Если указатели встретились или пересеклись, не обнаружив несовпадения, подстрока является палиндромом. Сохраняйте самую длинную из найденных.

Чтобы разрешить равенство по длине, перебирайте начальные позиции слева направо и заменяйте лучший результат, только если новый палиндром строго длиннее. Тогда более поздний палиндром той же длины никогда не вытеснит более ранний, и вы вернёте самый левый.

Этот алгоритм рассматривает все n(n+1)/2 подстрок, поэтому он не может пропустить ответ. Он медленный, потому что при каждой проверке указатели могут пройти половину подстроки. Для строки из 2000 символов a каждая подстрока является палиндромом, и при каждой проверке указатели доходят до середины: примерно n³/12 ≈ 6.7 × 10^8 сравнений букв.

Алгоритм

Начните с лучшего результата — первой буквы: начальная позиция 0, длина 1.
Для каждой начальной позиции i и каждого конца j ≥ i сравнивайте буквы с обоих концов по направлению к середине, пока они не различатся или указатели не встретятся.
Если указатели встретились и несовпадений не было, s[i..j] — палиндром.
Если его длина j-i+1 больше длины лучшего результата, сохраните i и эту длину.
Верните подстроку, начинающуюся с лучшей начальной позиции и имеющую лучшую длину.

def longestPalindrome(s):
    n = len(s)
    best_start, best_len = 0, 1
    for i in range(n):
        for j in range(i, n):
            # Compare s[i..j] from both ends toward the middle
            left, right = i, j
            while left < right and s[left] == s[right]:
                left += 1
                right -= 1
            is_palindrome = left >= right
            if is_palindrome and j - i + 1 > best_len:
                best_start, best_len = i, j - i + 1
    return s[best_start:best_start + best_len]

Таблица палиндромов по длине

Идея

Метод перебора с возвратом забывает то, что уже узнал. Проверяя "anana", он сравнивает a с a, затем n с n, и второе сравнение — это вся проверка "nan", которую он уже выполнял. Правило, которое позволяет сэкономить работу: s[i..j] — палиндром, если его крайние символы совпадают, а часть между ними, s[i+1..j-1], — палиндром. Одно сравнение и один сохранённый ответ определяют каждый подстроку.

Сохраняй ответы в таблице pal[i][j] и заполняй её по длине. Каждая одиночная буква — палиндром. Подстрока из двух букв является палиндромом, если обе буквы совпадают. Для большей длины используй правило: внутренняя часть на две буквы короче, поэтому её ячейка уже заполнена.

В "bananas" значение pal[1][5] ("anana") равно true, потому что s[1] и s[5] — обе буквы a, а pal[2][4] ("nan") равно true. Длины увеличиваются, а начальные позиции идут слева направо, поэтому первый палиндром новой рекордной длины также является самым левым палиндромом этой длины. Примерно n²/2 ячеек требуют по O(1) времени каждая, поэтому время работы составляет O(n²); цена — память: 4 × 10^6 ячеек при n = 2000.

Алгоритм

Создайте таблицу размером n × n pal, заполненную значениями false.
Для каждой длины от 1 до n и каждого начального индекса i, для которого конечный индекс j = i+length-1 остаётся внутри строки, проверьте две крайние буквы.
Отметьте pal[i][j], если они совпадают, а длина не превышает 2 или pal[i+1][j-1] имеет значение true.
Когда длина отмеченной ячейки превышает текущий лучший результат, сохраните i и длину.
Верните подстроку, начинающуюся с лучшего начального индекса.

def longestPalindrome(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways
    pal = [[False] * n for _ in range(n)]
    best_start, best_len = 0, 1
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Equal ends, and the part inside them is a palindrome (or too short to matter)
            if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]):
                pal[i][j] = True
                if length > best_len:
                    best_start, best_len = i, length
    return s[best_start:best_start + best_len]

Расширяйтесь вокруг каждого центра

Идея

У каждого палиндрома есть центр. Палиндром нечётной длины, например "anana", имеет центром букву; палиндром чётной длины, например "abba", — промежуток между двумя средними буквами. Строка длины n содержит n букв и n-1 промежутков, поэтому всего возможных центров 2n-1.

От центра двигайтесь наружу, на одну букву с каждой стороны, пока буквы совпадают. Каждый шаг доказывает, что существует палиндром на две буквы длиннее. Первое несовпадение или край строки завершает обход, и палиндром большей длины не может иметь тот же центр, потому что он содержал бы несовпадающую пару. Значит, одного обхода наружу достаточно, чтобы найти самый длинный палиндром вокруг каждого центра, а самый длинный из них и будет ответом.

В строке "bananas" начните с буквы a с индексом 3. Буквы с индексами 2 и 4 — обе n, буквы с индексами 1 и 5 — обе a, а буквы с индексами 0 и 6 — b и s, поэтому обход останавливается на длине 5. Начальная позиция — 3 - (5-1)/2 = 1, что даёт "anana". Та же формула, center - (length-1)/2 с округлением вниз, работает и для центров-промежутков.

Обходите центры слева направо и заменяйте лучший результат только при строго большей длине. У двух палиндромов одинаковой длины чётность совпадает, а тот, у которого центр расположен раньше, начинается раньше, поэтому выигрывает самый левый. Худший случай — строка из повторяющихся одинаковых букв: каждый центр проходит до ближайшего края, примерно n²/2 = 2 × 10^6 шагов при n = 2000, а памяти требуется всего несколько целых чисел.

Алгоритм

Напишите expand(left, right): пока оба индекса находятся внутри строки и буквы совпадают, уменьшайте left и увеличивайте right. Верните right-left-1.
Для каждого центра от 0 до n-1 возьмите большее из значений expand(center, center) и expand(center, center+1).
Если эта длина больше лучшей, установите начало лучшего фрагмента на center - (length-1)/2, округлив вниз, а его длину — равной этой длине.
Верните подстроку, начинающуюся с лучшего начала и имеющую лучшую длину.

def expand(s, left, right):
    # Grow outward while the two ends match; return the palindrome's length
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1


def longestPalindrome(s):
    best_start, best_len = 0, 1
    for center in range(len(s)):
        # Odd lengths grow from one letter, even lengths from the gap after it
        length = max(expand(s, center, center), expand(s, center, center + 1))
        if length > best_len:
            best_start = center - (length - 1) // 2
            best_len = length
    return s[best_start:best_start + best_len]

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

Идея проста, поэтому ошибки скрываются в деталях: центры между символами, длина после прохода, правило разрешения равенства и срезы.

Расширение только вокруг букв пропускает все чётные палиндромы. Для "abba" это вернёт "a" вместо "abba".
Проход останавливается на одну позицию дальше каждого конца, поэтому палиндром — это s[left+1..right-1] длиной right-left-1. Использование right-left+1 добавляет две несовпадающие буквы.
Замена лучшего результата при равной длине возвращает самый правый палиндром: "abba" вместо "yzzy" для "xyzzyabba".
Для центра в промежутке center - length/2 даёт позицию на одну левее нужной. В "xyzzyabba" промежуток после индекса 2 имеет длину 4, а начало — 2 - (4-1)/2 = 1, а не 0.
У API для срезов разные правила: C++ substr и C# Substring принимают длину, а JavaScript substring и Java substring принимают конечный индекс.
В таблице заполнение строк по начальному индексу от 0 вверх приводит к чтению pal[i+1][j-1] до того, как оно заполнено. Заполняйте таблицу по длине или перебирайте начальные индексы с конца.

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

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

Расширение от центра требует времени O(n²) и дополнительной памяти O(1). Табличный подход также требует времени O(n²), но занимает память O(n²), а проверка каждой подстроки требует времени O(n³). Алгоритм Манакера достигает сложности O(n), но интервьюеры редко ожидают его знания.

Почему при расширении вокруг центра используется 2n-1 центров?

Палиндром нечётной длины имеет среднюю букву, а палиндром чётной длины — промежуток посередине между двумя одинаковыми буквами. Строка из n букв содержит n букв и n-1 промежутков между соседними буквами. Если расширяться только от букв, можно пропустить палиндромы, такие как "abba".

Что такое алгоритм Манакера?

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

Чем самая длинная палиндромная подстрока отличается от самой длинной палиндромной подпоследовательности?

Подстрока — это последовательность идущих подряд букв, а подпоследовательность может пропускать буквы. В "character" самая длинная палиндромная подстрока — "ara", но "carac" — палиндромная подпоследовательность длины 5. Вариант с подпоследовательностью решается с помощью таблицы для (i, j), в которой отбрасывается один из концов, если они различаются.

Python

def longestPalindrome(s):
    # Напишите код здесь

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

Случай 1

Случай 2

Случай 3

Ввод

s = "bananas"

Ожидается

"anana"

Longest Palindromic Substring

Функция

Ограничения

Примеры

Подсказки

Решение

Проверь каждую подстроку

Таблица палиндромов по длине

Расширяйтесь вокруг каждого центра

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

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

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