package main


func longestPalindrome(s string) string {
    if len(s) <= 1 {
        return s
    }
    table := make([][]bool, len(s))
    for i := 0; i < len(table); i++ {
        table[i] = make([]bool, len(s))
    }
    
    b := 0
    e := 1
    for l := 0; l < len(s); l++ {
        for i := 0; i < len(s) - l; i++ {
            j := i + l
            if l == 0 {
                table[i][j] = true
            } else if l == 1 {
                table[i][j] = s[i] == s[j]
            } else {
                table[i][j] = table[i+1][j-1] && (s[i] == s[j])
            }
            if table[i][j] {
                b, e = i, j
            }
        }
    }
    return s[b:e+1]
}


func longestPalindrome2(s string) string {
    if len(s) <= 1 {
        return s
    }
    table := make([][]int, len(s))
    for i := 0; i < len(table); i++ {
        table[i] = make([]int, len(s))
    }
    var res string
    max := 0
    for i, _ := range s{
        for j := i; j > -1; j-- {
            if s[i] == s[j] && (i - j < 2 || table[i - 1][j + 1] != 0) {
                table[i][j] = 1
            }

            if table[i][j] != 0 && (i - j + 1) > max {
                    max = i - j + 1
                    res = s[j:i + 1]
            }
        }
    }
    return res
}

func t(size int) {
    table := make([][]int, size)
    for i := 0; i < len(table); i++ {
        table[i] = make([]int, size)
    }
    //total := 0
    for i := 0; i < size; i++ {
        for j :=0; j < size; j++ {
            table[i][j] = i + j
            //total += (i + j)
        }
    }
}


func main() {
    //j := 10
    s := "ZnVuYyBsb25nZXN0UGFsaW5kcm9tZShzIHN0cmaabbaabbaabbluZykgc3RyaW5nIHsKICAgIGlmIGxlbihzKSA8PSAxIHsKICAgICAgICByZXR1cm4gcwogICAgfQogICAgCiAgICB0YWJsZSA6PaaabbbaaabbbaaaSBtYWtlKFtdW11ib29"
    for i := 0; i < 0; i++ {
        s = s + s
        
        //j += j
        //j -= j/2

        //t(1000)
    }
    //assert(j == 10)
	
    result := longestPalindrome2(s)
	assert(result == "aaabbbaaabbbaaa")
    

    //assert(longestPalindrome("aa") == "aa")
}