5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

// 暴力法
func longestPalindrome(s string) string {

    // 先在每一个字符串左右 拼接上'#'字符
    ns := addRune(s, '#')

    srune := []rune(ns)

    var result string
    for index, _ := range srune {
        // 向左右两边扩展，判断字符串是否是回文字符
        i, j := index, index
        for {
            if i < 0 || j > len(ns)-1 || srune[i] != srune[j] {
                break
            }
            if j-i >= len(result) && i > -1 && j < len(ns) {
                result = string(srune[i : j+1])
            }
            if srune[i] == srune[j] {
                i--
                j++
            }
        }
    }
    return removRune(result, '#')
}

func addRune(str string, char rune) string {
    st := []rune(str)
    nst := make([]rune, 0)

    for _, s1 := range st {
        nst = append(nst, char)
        nst = append(nst, s1)
    }
    nst = append(nst, char)
    return string(nst)
}

func removRune(str string, char rune) string {
    st := []rune(str)
    nst := make([]rune, 0)

    for index, s1 := range st {
        if index%2 == 0 {
            continue
        }
        nst = append(nst, s1)
    }
    return string(nst)
}