Задача.

Дана строка. Нужно найти самую длинную подстроку, которая является палиндромом.
Например,
Для "babad", ответ "bab" или "aba"
Для "cbbd", ответ "bb"
Для "abaxyzzyxb", ответ "xyzzyx".

Ссылка на leetcode: https://leetcode.com/problems/longest-palindromic-substring/

Решение.

Рассмотрим на примере строки "abaxyzzyxb":

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

Самый длинный из которых это xyzzyx.

Я уже публиковал решение задачи на проверку того, является ли строка палиндромом или нет: Проверка на палиндром

Если кратко, то мы используем подход Two Pointers (два указателя). Используем два указателя. Один указывает на начало строки, а второй на конец. Если символы, на которые они указывают не равны - то строка не палиндром. Если равны - сдвигаем указатели в направлении к середине строки (левый указатель сдвигаем вправо, а правый сдвигаем влево).

boolean isPalindrome(String s, int start, int end) {
    while (start < end) {
        if (s.charAt(start) != s.charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

Эта проверка работает за O(n).
Чтобы решить исходную задачу - мы можем сгенерировать все возможные подстроки и проверить, не являются ли они палиндромами и выбрать среди них самый длинный.
Это можно сделать так:

for (int i = 0; i < s.length(); i++) {
    for (int j = i; j < s.length(); j++) {
        if (isPalindrome(s, i, j)) {
            ....
        }
    }
}

Такой алгоритм работает за O(n^3), т.к. у нас два вложенных цикла и внутри еще проверка на палиндром.

Полный код решения:

class Solution {
    public String longestPalindrome(String s) {
        int maxLen = 0;
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if (isPalindrome(s, i, j)) {
                    int len = j - i + 1;
                    if (len > maxLen) {
                        maxLen = len;
                        start = i;
                        end = j;
                    }
                }
            }
        }
        return s.substring(start, end + 1);
    }

    private boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

Time Complexity O(n^3), Space Complexity O(1).

Можно ли улучшить это решение? Да, можно.

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

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

Для этого можно изменить подход в определении того, что строка является палинромом или нет. Мы можем вместо того, чтобы задавать начало и конец подстроки для проверки, задавать только лишь центр подстроки и при проверке на палиндром идти от центра к краям.

Например, если мы рассматриваем строку "abaxyzzyxb". Одном из потенциальных центров палидромической подстроки является промежуток между буквами z.

Задав этот центр, мы может идти от него к краям и проверять, является ли текущая подстрока палиндромом или нет. По итерациям это выглядит так:

В коде такую проверку можно реализовать следующим образом (от центра к краям). В качестве результата вернем индексы максимального палиндрома начинающегося в заданном центре (вначале left и right указывают на один и тот же символ/центр или на соседнии, если центр это промежуток между символами):

private int[] getPalindromeStartAndEndIndexes(String s, int left, int right) {
    while (left >= 0 && right < s.length()) {
        if (s.charAt(left) != s.charAt(right)) {
            break;
        }
        left--;
        right++;
    }
    return new int[] {left + 1, right - 1};
}

Хорошо, мы избавились от необходимости задания начала и конца подстрок. Нам нужно в цикле пройтись по всем потенциальным центрам палиндромов. Тут важно заметить, что для палиндромов нечетной длинны, центр это конкретный символ. А для четной - это промежуток между символами.

Вначале, центр потенциального палиндрома это первый символ строки и начальные значения left и right равны и указывают на этот первый символ:

Далее в проверке на палиндром мы будем расширяться влево и вправо от этого центра и найдем максимальный палиндром, центр которого это первый символ.

Далее мы перейдем к новому потенциальному центру - промежутку между певым и вторым символом:

После проверки всех палиндромов, центр которых это промежуток между первым и вторым символом, перейдем к следующему потенциальному центру - второму символу строки и т.д.

В коде это будет выглядеть так:

class Solution {
    public String longestPalindrome(String s) {
        int maxLen = 0;
        int start = 0;
        int end = 0;
        for (int center = 0; center < s.length() * 2; center++) {
            int left = 0;
            int right = 0;
            if (center % 2 == 0) {
                left = center / 2;
                right = left;
            } else {
                left = center / 2;
                right = left + 1;
            }
            int[] startAndEndIndexes = getPalindromeStartAndEndIndexes(s, left, right);
            int currentStart = startAndEndIndexes[0];
            int currentEnd = startAndEndIndexes[1];
            int len = currentEnd - currentStart + 1;
            if (len > maxLen) {
                maxLen = len;
                start = currentStart;
                end = currentEnd;
            }
        }
        return s.substring(start, end + 1);
    }

    private int[] getPalindromeStartAndEndIndexes(String s, int left, int right) {
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            left--;
            right++;
        }
        return new int[] {left + 1, right - 1};
    }
}

Это решение работает за O(n^2). Space complexity O(1).