package main

import "fmt"

func main() {
	str := "ababd"
	fmt.Println(longestPalindrome(str))
}

func longestPalindrome(s string) string {
	n := len(s)
	if n <= 1 {
		return s
	}
	max := func(a , b int) int {
		if a > b {
			return  a
		}
		return b
	}
	dp := make([][]bool,0)
	maxLen , code  := 0 , []int{0,1}
	for i := 0 ; i < n ; i ++ {
		dp = append(dp,make([]bool,n))
		dp[i][i] = true
	}
	// 斜向遍历/初始化 , 填充dp
	for diff := 1 ; diff < n ; diff ++ {
		for index := 0 ; index + diff < n ; index ++ {
			i , j  := index , index + diff
			dp[i][j] = (diff == 1 || dp[i+1][j-1]) && s[i] == s[j]
			if maxLen = max(maxLen , diff) ; dp[i][j] && maxLen == diff {
				code[0] , code[1] = i , j + 1
			}
		}
	}
	return s[code[0]:code[1]]
}