Длиннейшая палиндромная подстрока

Длиннейшая палиндромная подстрока

Задача

Найти самую длинную подстроку-палиндром в строке. Палиндром читается одинаково в обе стороны (например, "racecar", "noon").

Для примера:

• longest_palindrome("babad") → "bab" или "aba"
• longest_palindrome("cbbd") → "bb"

Решение 1: Expand Around Center (O(n²), оптимально)

Для каждого символа (или пары символов) как центра, расширяем вправо и влево, пока символы совпадают.

def longestPalindrome_expand(s):
    """
    Expand around center метод.
    
    Идея:
    - Палиндром имеет центр: нечётной (один символ) или чётной (два символа) длины
    - Для каждого возможного центра расширяем влево и вправо
    - Отслеживаем самый длинный найденный палиндром
    
    Временная сложность: O(n²) — для каждого из O(n) центров расширяем за O(n)
    Пространственная сложность: O(1) — кроме результата
    """
    if not s:
        return ""
    
    def expand_around_center(left, right):
        """Расширяет из центра (left, right) и возвращает (start, length)."""
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # Возвращаем индекс начала и длину палиндрома
        return left + 1, right - left - 1
    
    start = 0
    max_len = 0
    
    for i in range(len(s)):
        # Нечётной длины палиндром (один центр)
        s1, len1 = expand_around_center(i, i)
        
        # Чётной длины палиндром (два центра)
        s2, len2 = expand_around_center(i, i + 1)
        
        # Выбираем более длинный
        if len1 > max_len:
            start, max_len = s1, len1
        if len2 > max_len:
            start, max_len = s2, len2
    
    return s[start:start + max_len]

# Тестирование
print(longestPalindrome_expand("babad"))    # "bab" или "aba"
print(longestPalindrome_expand("cbbd"))     # "bb"
print(longestPalindrome_expand("a"))        # "a"
print(longestPalindrome_expand("racecar")) # "racecar"
print(longestPalindrome_expand("noon"))    # "noon"
print(longestPalindrome_expand(""))        # ""

Решение 2: Dynamic Programming (O(n²))

Строим таблицу где dp[i][j] = true если подстрока от i до j — палиндром.

def longestPalindrome_dp(s):
    """
    DP подход.
    
    dp[i][j] = True если s[i:j+1] — палиндром
    
    Переходы:
    - Если i == j: dp[i][j] = True (один символ)
    - Если j == i + 1: dp[i][j] = (s[i] == s[j]) (два символа)
    - Иначе: dp[i][j] = (s[i] == s[j]) AND dp[i+1][j-1]
    
    Временная сложность: O(n²)
    Пространственная сложность: O(n²)
    """
    if not s:
        return ""
    
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start = 0
    max_len = 1
    
    # Длина 1
    for i in range(n):
        dp[i][i] = True
    
    # Длина 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_len = 2
    
    # Длина 3 и больше
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                start = i
                max_len = length
    
    return s[start:start + max_len]

print(longestPalindrome_dp("babad"))    # "bab" или "aba"
print(longestPalindrome_dp("cbbd"))     # "bb"

Решение 3: Манахеров алгоритм (O(n), оптимальный)

Манахеров алгоритм — это O(n) алгоритм поиска всех палиндромов.

Идея: используем информацию из уже найденных палиндромов, чтобы не перепроверять.

def longestPalindrome_manacher(s):
    """
    Манахеров алгоритм — линейное решение.
    
    Идея:
    1. Добавляем специальные символы (#) между символами
    2. Отслеживаем диапазон максимального палиндрома
    3. Используем информацию о симметрии
    
    Временная сложность: O(n)
    Пространственная сложность: O(n)
    """
    if not s:
        return ""
    
    # Преобразуем строку: "abc" → "#a#b#c#"
    # Это предотвращает проблемы с нечётными палиндромами
    transformed = "#".join("^{}$".format(s))
    n = len(transformed)
    
    # p[i] = радиус палиндрома с центром в i
    p = [0] * n
    center = 0  # центр максимального палиндрома
    right = 0   # правая граница максимального палиндрома
    max_len = 0
    max_center = 0
    
    for i in range(1, n - 1):
        # mirror = 2*center - i (зеркальная позиция)
        mirror = 2 * center - i
        
        # Если i внутри известного палиндрома, используем информацию
        if i < right:
            p[i] = min(right - i, p[mirror])
        
        # Пробуем расширить палиндром с центром в i
        try:
            while transformed[i + p[i] + 1] == transformed[i - p[i] - 1]:
                p[i] += 1
        except IndexError:
            pass
        
        # Обновляем центр и правую границу
        if i + p[i] > right:
            center = i
            right = i + p[i]
        
        # Отслеживаем максимум
        if p[i] > max_len:
            max_len = p[i]
            max_center = i
    
    # Извлекаем результат из трансформированной строки
    start = (max_center - max_len) // 2
    return s[start:start + max_len]

print(longestPalindrome_manacher("babad"))    # "bab" или "aba"
print(longestPalindrome_manacher("cbbd"))     # "bb"
print(longestPalindrome_manacher("racecar")) # "racecar"

Пошаговое выполнение для "cbbd"

Expand Around Center подход:

Центр в индексе 0 (c):
  Нечётной: [0,0] → "c" (длина 1)
  Чётной: [0,1] → c≠b, нет

Центр в индексе 1 (b):
  Нечётной: [1,1] → "b" (длина 1)
  Чётной: [1,2] → b=b, [0,3] → c≠d, стоп
    → "bb" (длина 2) ← МАКСИМУМ

Центр в индексе 2 (b):
  Нечётной: [2,2] → "b" (длина 1)
  Чётной: [2,3] → b≠d, нет

Центр в индексе 3 (d):
  Нечётной: [3,3] → "d" (длина 1)
  Чётной: [3,4] → индекс вне границ

Результат: "bb"

Сравнение подходов

Варианты задачи

1. Длиннейшая палиндромная подпоследовательность (не подстрока):

def longestPalindromeSubsequence(s):
    """
    Подпоследовательность (не обязательно непрерывная).
    Используем LCS с обратной строкой.
    """
    def lcs(s1, s2):
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        return dp[m][n]
    
    return lcs(s, s[::-1])

print(longestPalindromeSubsequence("babad"))  # 5 ("bab" or "aba")

2. Количество палиндромных подстрок:

def countPalindromes(s):
    """
    Подсчитывает все палиндромные подстроки.
    """
    if not s:
        return 0
    
    count = 0
    
    def expand(left, right):
        nonlocal count
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    
    for i in range(len(s)):
        expand(i, i)      # нечётной длины
        expand(i, i + 1)  # чётной длины
    
    return count

print(countPalindromes("babad"))  # 6 ("b", "a", "b", "d", "bab", "aba")

Интуиция Expand Around Center

Ключевой момент: палиндром симметричен относительно своего центра.

• Нечётной длины палиндром: один центр (символ)
• Чётной длины палиндром: два центра (два одинаковых символа)

Заключение

Longest Palindromic Substring — важная задача с несколькими решениями:

1. Expand Around Center (O(n²)) — просто, интуитивно, рекомендуется
2. Dynamic Programming (O(n²)) — классический DP подход
3. Манахеров алгоритм (O(n)) — продвинутое, редко требуется на интервью

Для интервью достаточно знать Expand Around Center. Если спросят про оптимизацию, говорите про Манахеров.