// MARK: - 5. Longest Palindromic Substring
// Дана строка s, вернуть самую длинную палиндромную строку

// Проходимся по букве и разрастанием строки вправо и влево проверяем палендром она или нет

// babzzbad

func longestPalindrome(_ s: String) -> String {
    let s = Array(s).map{String($0)}

    // для собеса
    // var result = [String]()
    var result: Array<String>.SubSequence = []
    var maxLength = 0

    for i in 0..<s.count {

        // нечетные палиндромы
        var l = i
        var r = i

        while l >= 0 && r < s.count && s[r] == s[l] {
            if r - l + 1 > maxLength {
                maxLength = r - l + 1
                result = s[l...r]
            }
            l -= 1
            r += 1
        }

        // четные палиндромы. захватываем 2 элемента и разрастаемся
        l = i
        r = i+1

        while l >= 0 && r < s.count && s[r] == s[l] {
            if r - l + 1 > maxLength {
                maxLength = r - l + 1
                result = s[l...r]
            }
            l -= 1
            r += 1
        }
    }
    return result.joined()
}