Поиск максимальной подстроки-палиндрома

Поиск максимальной подстроки-палиндрома

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

Решение 1: Расширение от центра — O(n²) время, O(1) пространство

Основная идея: для каждой возможной позиции центра разверните палиндром во все стороны.

public class LongestPalindrome {
    /**
     * Поиск самой длинной подстроки-палиндрома методом расширения от центра
     * Время: O(n²)
     * Пространство: O(1)
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        
        int start = 0;
        int maxLen = 0;
        
        // Проверяем каждую позицию как центр палиндрома
        for (int i = 0; i < s.length(); i++) {
            // Палиндромы нечетной длины (центр в i)
            int len1 = expandAroundCenter(s, i, i);
            
            // Палиндромы четной длины (центр между i и i+1)
            int len2 = expandAroundCenter(s, i, i + 1);
            
            // Берем максимальную длину
            int len = Math.max(len1, len2);
            
            // Обновляем результат, если нашли более длинный палиндром
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;  // вычисляем начальную позицию
            }
        }
        
        return s.substring(start, start + maxLen);
    }
    
    /**
     * Расширяем палиндром от центра (left, right)
     * Возвращаем длину найденного палиндрома
     */
    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;   // расширяем влево
            right++;  // расширяем вправо
        }
        
        // Возвращаем длину палиндрома
        // (right - left - 1) потому что мы вышли за границы
        return right - left - 1;
    }
    
    public static void main(String[] args) {
        System.out.println(longestPalindrome("babad"));    // "bab" или "aba"
        System.out.println(longestPalindrome("cbbd"));     // "bb"
        System.out.println(longestPalindrome("a"));        // "a"
        System.out.println(longestPalindrome("ac"));       // "a" или "c"
        System.out.println(longestPalindrome("abacabad")); // "abacaba"
        System.out.println(longestPalindrome("racecar")); // "racecar"
    }
}

Как это работает для "babad":

i=0 (a): нечет {a}, четн {ab} -> max len = 1
i=1 (b): нечет {bab}, четн {ba} -> max len = 3 (bab)
i=2 (a): нечет {aba}, четн {ab} -> уже есть bab длины 3
i=3 (b): нечет {b}, четн {ba} -> max len = 3
i=4 (d): нечет {d}, четн {} -> max len = 3

Результат: "bab" (или "aba" тоже валидно)

Решение 2: Динамическое программирование — O(n²) время, O(n²) пространство

Используем таблицу для мемоизации результатов:

public class LongestPalindromeDP {
    /**
     * Решение с динамическим программированием
     * Время: O(n²)
     * Пространство: O(n²)
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        
        int n = s.length();
        // dp[i][j] = true, если подстрока от i до j является палиндромом
        boolean[][] dp = new boolean[n][n];
        
        int start = 0;
        int maxLen = 1;
        
        // Диагональ: каждый символ сам по себе палиндром
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        // Проверяем подстроки длины 2
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                start = i;
                maxLen = 2;
            }
        }
        
        // Проверяем подстроки длины 3 и больше
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;  // конец подстроки
                
                // Если крайние символы совпадают и внутренняя часть палиндром
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    start = i;
                    maxLen = len;
                }
            }
        }
        
        return s.substring(start, start + maxLen);
    }
    
    public static void main(String[] args) {
        System.out.println(longestPalindrome("babad"));    // "bab"
        System.out.println(longestPalindrome("cbbd"));     // "bb"
        System.out.println(longestPalindrome("abacabad")); // "abacaba"
    }
}

Таблица DP для "babad":

    b a b a d
  ---------
b | T T T F F
a | _ T T T F
b | _ _ T F F
a | _ _ _ T F
d | _ _ _ _ T

T = палиндром, _ = не проверено

Итог: "bab" и "aba" оба являются палиндромами длины 3

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

Самый быстрый, но сложный для понимания:

public class LongestPalindromeManacher {
    /**
     * Алгоритм Манахера для поиска палиндрома за O(n)
     * Очень быстро, но сложен для понимания
     * Время: O(n)
     * Пространство: O(n)
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        
        // Преобразуем строку, добавив разделители для унификации
        // "abc" -> "#a#b#c#"
        String t = "#";
        for (char c : s.toCharArray()) {
            t += c + "#";
        }
        
        int[] p = new int[t.length()];  // длины палиндромов
        int center = 0;  // центр палиндрома
        int right = 0;   // правая граница
        
        int maxLen = 0;
        int centerIndex = 0;
        
        for (int i = 1; i < t.length() - 1; i++) {
            int mirror = 2 * center - i;
            
            if (i < right) {
                p[i] = Math.min(right - i, p[mirror]);
            }
            
            // Расширяем палиндром
            while (t.charAt(i + p[i] + 1) == t.charAt(i - p[i] - 1)) {
                p[i]++;
            }
            
            // Обновляем центр и правую границу
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
            
            // Сохраняем самый длинный палиндром
            if (p[i] > maxLen) {
                maxLen = p[i];
                centerIndex = i;
            }
        }
        
        // Восстанавливаем исходную строку
        int start = (centerIndex - maxLen) / 2;
        return s.substring(start, start + maxLen);
    }
}

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

На собеседовании

1. Начните с подхода расширения от центра
2. Объясните почему нужно проверять нечетные и четные палиндромы
3. Реализуйте полное решение
4. Обсудите сложность
5. Упомяните альтернативы (DP, Манахер) но не углубляйтесь
6. Тестируйте на примерах

Граничные случаи

• Пустая строка: вернуть ""
• Одиночный символ: вернуть его
• Два одинаковых символа: "aa" -> "aa"
• Палиндром по всей длине: "racecar" -> "racecar"
• Нет палиндромов длины > 1: "abcd" -> любой символ