Самая длинная палиндромная подстрока
Tags: algorithms, interview
Published: 2023-08-04 11:16:36



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

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

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kw8aw46kq4yvtp8f5xj0.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ajtgbgojcdqkvmbdtun0.png)

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

Я уже публиковал решение задачи на проверку того, является ли строка палиндромом или нет: [Проверка на палиндром](https://dev.to/faangmaster/provierka-na-palindrom-3e7p)

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

```java
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)**. 
Чтобы решить исходную задачу - мы можем сгенерировать все возможные подстроки и проверить, не являются ли они палиндромами и выбрать среди них самый длинный.
Это можно сделать так:

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

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

Полный код решения:
```java
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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/59djum60iki6u57h1jux.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rgvktgkmm97wtg9k4i2c.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zsk6fmlewid1b1schtq4.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jw4cbp740ci6cfegtday.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q3ch51r21sglkyxttdhg.png)

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

```java
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 равны и указывают на этот первый символ:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/htncafaojaz71rkr3hfx.png)

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

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5flgtdhjlzott3ergfi4.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8860tqlnkz9i59xgp6qo.png)
В коде это будет выглядеть так:

```java
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).**