5. Longest Palindromic Substring

Задача

Дана строка s. Верните самую длинную палиндромную подстроку в s.

Примеры

Пример 1

Input: s = "babad"
Output: "bab"

Пояснение

“aba” тоже является допустимым ответом.

Пример 2

Input: s = "cbbd"
Output: "bb"

Решение

Решение

/**
 * Time:  O(n^2)  — для каждого центра (их ~2n) расширяемся в худшем случае до n
 * Space: O(1)    — только несколько переменных
 */
var longestPalindrome = function(s) {
    if (s.length <= 1) return s;
 
    // Лучший найденный палиндром храним границами [bestLeft, bestRight] (включительно).
    let bestLeft = 0;
    let bestRight = 0;
 
    // Расширяемся от центра (left, right), пока подстрока остается палиндромом.
    function expand(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
 
        // После выхода из цикла мы "перерасширились" на 1 шаг, откатываемся внутрь.
        const palindromeLeft = left + 1;
        const palindromeRight = right - 1;
 
        // Обновляем лучший ответ, если нашли палиндром длиннее.
        if (palindromeRight - palindromeLeft > bestRight - bestLeft) {
            bestLeft = palindromeLeft;
            bestRight = palindromeRight;
        }
    }
 
    for (let center = 0; center < s.length; center++) {
        // Нечетный палиндром: центр в одном символе (например, "aba").
        expand(center, center);
 
        // Четный палиндром: центр между символами (например, "abba").
        expand(center, center + 1);
    }
 
    // substring: правая граница не включается, поэтому +1.
    return s.substring(bestLeft, bestRight + 1);
};

Решение 2 (Алгоритм Манакера)

/**
 * LeetCode 5: Longest Palindromic Substring
 * Алгоритм Манакера
 *
 * Time:  O(n) — rightBoundary движется только вправо, суммарно n шагов
 * Space: O(n) — трансформированная строка и массив радиусов p[]
 */
var longestPalindrome = function (s) {
    // Шаг 1: вставляем '#' между символами, чтобы унифицировать
    // нечётные и чётные палиндромы в одну модель.
    // "abc" → "#a#b#c#"
    const transformed = '#' + s.split('').join('#') + '#';
    const n = transformed.length;
 
    // p[i] = радиус палиндрома с центром в i (без учёта самого центра)
    // Пример: "#a#b#a#" → p[3] = 3, что соответствует "aba" длиной 3
    const p = new Array(n).fill(0);
 
    // center       — центр самого правого из найденных палиндромов
    // rightBoundary — его правая граница (не включительно)
    let center = 0;
    let rightBoundary = 0;
 
    let bestCenter = 0; // центр лучшего найденного палиндрома
 
    for (let i = 0; i < n; i++) {
        // Зеркало: симметричная позиция i относительно center
        const mirror = 2 * center - i;
 
        // Если i внутри известного палиндрома — берём радиус зеркала
        // как минимальную стартовую точку, а не начинаем с 0.
        // Math.min нужен, чтобы не выйти за правую границу.
        if (i < rightBoundary) {
            p[i] = Math.min(rightBoundary - i, p[mirror]);
        }
 
        // Пробуем расширить палиндром вокруг i дальше стартовой точки
        let left = i - (p[i] + 1);
        let right = i + (p[i] + 1);
        while (left >= 0 && right < n && transformed[left] === transformed[right]) {
            p[i]++;
            left--;
            right++;
        }
 
        // Если вышли за правую границу — обновляем "самый правый" палиндром
        if (i + p[i] > rightBoundary) {
            center = i;
            rightBoundary = i + p[i];
        }
 
        // Фиксируем лучший результат
        if (p[i] > p[bestCenter]) {
            bestCenter = i;
        }
    }
 
    // Шаг 2: переводим координаты обратно в исходную строку.
    // p[bestCenter] — это ровно длина палиндрома в оригинальной строке.
    const startIndex = (bestCenter - p[bestCenter]) / 2;
    return s.substring(startIndex, startIndex + p[bestCenter]);
};