4. Longest Palindromic Substring

Вход:  s = "babad"
Выход: "bab" (или "aba")

Вход:  s = "cbbd"
Выход: "bb"

Строка:   a   b   a   b   a
Центры:  [0]  |  [1]  |  [2]  |  [3]  |  [4]
         Нечет Чет Нечет Чет Нечет Чет Нечет Чет Нечет

package palindrome

// LongestPalindrome находит наибольшую палиндромную подстроку за O(N^2) времени и O(1) памяти.
func LongestPalindrome(s string) string {
    if len(s) < 2 {
        return s
    }

    start, maxLen := 0, 1

    for i := 0; i < len(s); i++ {
        // Нечетный палиндром: центр s[i] (например, "aba")
        len1 := expandAroundCenter(s, i, i)
        // Четный палиндром: центр между s[i] и s[i+1] (например, "abba")
        len2 := expandAroundCenter(s, i, i+1)

        currLen := max(len1, len2)
        if currLen > maxLen {
            maxLen = currLen
            start = i - (currLen-1)/2
        }
    }

    // Срез строки в Go не копирует байты — O(1) возврат 16-байтового заголовка
    return s[start : start+maxLen]
}

// expandAroundCenter возвращает длину палиндрома с заданным центром
func expandAroundCenter(s string, left, right int) int {
    for left >= 0 && right < len(s) && s[left] == s[right] {
        left--
        right++
    }
    // Длина между (left+1) и (right-1) включительно:
    // (right - 1) - (left + 1) + 1 = right - left - 1
    return right - left - 1
}

// LongestPalindromeUnicode корректно обрабатывает произвольные руны Unicode.
// Временная сложность: O(N^2)
// Пространственная сложность: O(N) — аллокация среза []rune
func LongestPalindromeUnicode(s string) string {
    if len(s) < 2 {
        return s
    }

    runes := []rune(s)
    n := len(runes)
    start, maxLen := 0, 1

    for i := 0; i < n; i++ {
        len1 := expandRunes(runes, i, i, n)
        len2 := expandRunes(runes, i, i+1, n)

        currLen := max(len1, len2)
        if currLen > maxLen {
            maxLen = currLen
            start = i - (currLen-1)/2
        }
    }

    return string(runes[start : start+maxLen])
}

func expandRunes(runes []rune, left, right, n int) int {
    for left >= 0 && right < n && runes[left] == runes[right] {
        left--
        right++
    }
    return right - left - 1
}

// LongestPalindromeManacher находит палиндром за строго линейное время O(N).
func LongestPalindromeManacher(s string) string {
    if len(s) < 2 {
        return s
    }

    // 1. Преобразование строки: "aba" -> "^#a#b#a#$"
    // Специальные символы '^' и '$' исключают проверки выхода за границы среза
    t := make([]byte, 0, len(s)*2+3)
    t = append(t, '^')
    for i := 0; i < len(s); i++ {
        t = append(t, '#', s[i])
    }
    t = append(t, '#', '$')

    n := len(t)
    p := make([]int, n) // p[i] — радиус палиндрома вокруг t[i]
    c, r := 0, 0        // c — центр самого правого палиндрома, r — его правая граница

    for i := 1; i < n-1; i++ {
        mirror := 2*c - i // Зеркальная позиция i относительно центра c

        if i < r {
            p[i] = min(r-i, p[mirror])
        }

        // Дорасширение палиндрома (выполняется амортизировано O(1) раз)
        for t[i+1+p[i]] == t[i-1-p[i]] {
            p[i]++
        }

        // Если палиндром с центром i вышел за правую границу r — сдвигаем окно
        if i+p[i] > r {
            c = i
            r = i + p[i]
        }
    }

    // Поиск максимального радиуса
    maxLen, centerIndex := 0, 0
    for i := 1; i < n-1; i++ {
        if p[i] > maxLen {
            maxLen = p[i]
            centerIndex = i
        }
    }

    // Восстановление исходных координат в оригинальной строке s
    start := (centerIndex - maxLen) / 2
    return s[start : start+maxLen]
}