Определить наибольший палиндром в строке

Условие

Дана строка, в которой могут встречаться один или несколько палиндромов. Необходимо найти палиндром максимальной длины, присутствующий в этой строке.

Ответ

Для самой длинной палиндромной подстроки расширяйтесь от каждого нечётного и чётного центра. Это даёт O(n²) времени без сложной структуры данных.

Пример на Swift, где единица сравнения — Character:

func longestPalindrome(_ text: String) -> String {
    let chars = Array(text)
    guard !chars.isEmpty else { return "" }
    var bestStart = 0, bestLength = 1
    func expand(_ first: Int, _ second: Int) {
        var left = first, right = second
        while left >= 0 && right < chars.count && chars[left] == chars[right] {
            let length = right - left + 1
            if length > bestLength {
                bestStart = left; bestLength = length
            }
            left -= 1; right += 1
        }
    }
    for center in chars.indices {
        expand(center, center)
        expand(center, center + 1)
    }
    return String(chars[bestStart..<(bestStart + bestLength)])
}

Регистр, пробелы и знаки учитываются буквально. При равной длине остаётся первый найденный вариант. Это поиск непрерывной подстроки, не подпоследовательности; преобразование строки в массив требует O(n) памяти.