Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/description/

Решение

https://www.youtube.com/watch?v=sp9f7nQHqeQ&t=1s

Что стало понятно за 10 минут видео. Решение которое в нем предлагается, это проходиться по всей строке и поинтерами идти влево и вправо от начального индекса. 2 цикла. Относительного этого и делать нашу работу. + нужно учитывать edge case из-за которого вызов функции будет дублироваться.

Представим решение в коде на PHP

class Solution {

    /**
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
        $lenInput = strlen($s);
        $result = '';

        for ($i = 0; $i < $lenInput; $i++) {
            $tmp1 = $this->getSubstring($s, $i, $i);
            $tmp2 = $this->getSubstring($s, $i, $i + 1);

            if (strlen($tmp1) > strlen($result)) {
                $result = $tmp1;
            }

            if (strlen($tmp2) > strlen($result)) {
                $result = $tmp2;
            }
        }

        return $result;
    }

    private function getSubstring($s, $left, $right) {
        while ($left >= 0 && $right < strlen($s) && $s[$left] === $s[$right]) {
            $left -= 1;
            $right += 1;
        }

        return substr($s, $left + 1, $right - $left - 1);
    }
}

Решение гения

class Solution {

    /**
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
        $T = "^#".implode("#", str_split($s))."#$";
        $n = strlen($T);
        $P = array_fill(0, $n, 0);
        $C = $R = 0;
        for ($i = 1; $i < $n-1; $i++) {
            $P[$i] = ($R > $i) ? min($R - $i, $P[2*$C - $i]) : 0;
            while ($T[$i + 1 + $P[$i]] == $T[$i - 1 - $P[$i]])
                $P[$i]++;

            if ($i + $P[$i] > $R) {
                $C = $i;
                $R = $i + $P[$i];
            }
        }
        $max_len = max($P);
        $center_index = array_search($max_len, $P);
        return substr($s, ($center_index - $max_len) / 2, $max_len);
    }
}

Этот код решает задачу нахождения самого длинного палиндромного подстроки строки s. Используется алгоритм Манакера (Manacher's Algorithm), который работает за O(n), позволяя находить палиндромные подстроки эффективно.