/**
 * @param s: input string
 * @return: a string as the longest palindromic substring
 */
// 暴力枚举
func LongestPalindrome(s string) string {
    // 最长向短遍历
	for length := len(s); length > 0; length-- {
		for start := 0; start+length <= len(s); start++ {
			if isPalindrome(s, start, start+length-1) {
				return s[start : start+length]
			}
		}
	}
	return ""
}

func isPalindrome(s string, left, right int) bool {
	for left < right && s[left] == s[right] {
		left++
		right--
	}
	return left >= right
}

/**
 * @param s: input string
 * @return: a string as the longest palindromic substring
 */
func LongestPalindrome(s string) string {
    res := ""
	for i := 0; i < len(s); i++ {
		res = getPalindromeFrom(s, i, i, res)
		res = getPalindromeFrom(s, i, i+1, res)
	}

	return res
}

func getPalindromeFrom(s string, left, right int, res string) string {
	sub := ""
	for left >= 0 && right < len(s) && s[left] == s[right] {
		sub = s[left : right+1]
		left--
		right++
	}
	if len(res) < len(sub) {
		return sub
	}
	return res
}

/**
 * @param s: input string
 * @return: a string as the longest palindromic substring
 */
// 动态规划
// 状态转移方程: dp[i][j] = (s[i] == s[j]) && ((j-i < 3) || dp[i+1][j-1])
func LongestPalindrome(s string) string {
	res, dp := "", make([][]bool, len(s))
	for i := 0; i < len(s); i++ {
		dp[i] = make([]bool, len(s))
	}
	for left := len(s) - 1; left >= 0; left-- {
		for right := left; right < len(s); right++ {
			dp[left][right] = (s[left] == s[right]) && ((right-left < 3) || dp[left+1][right-1])
			if dp[left][right] && (res == "" || right-left+1 > len(res)) {
				res = s[left : right+1]
			}
		}
	}
	return res
}