5 Longest Palindromic Substring

Method 1: Brute Force=> Pick all possible starting and ending positions, and then verify it is palindromic. O(n^3)

Method 2: DP => dp[i][j] (true if s[i][j] is palindromic and false if s[i][j] is not palindromic)

Method 3: Try each middle points and find the longest one.

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        ans = s[0]
        inc = 0.5
        while inc < len(s):
            if int(inc) == inc:
                tmp = s[int(inc)]
                j = 1
            else:
                tmp = ""
                j = 0.5
            while inc + j < len(s) and inc - j >=0 and s[int(inc + j)] == s[int(inc - j)]:
                tmp = s[int(inc - j)] + tmp + s[int(inc + j)]
                j = j + 1
                if len(ans) < len(tmp):
                    ans = tmp
            inc = 0.5 + inc
        return ans