# Python

• ``````def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# return self.driver(s, 0, len(s)-1)
dp = [[0 for i in range(len(s))] for j in range(len(s))]

if len(s) == 0: return None
if len(s) == 1: return s[0]
if len(s) == 2: return s if s[0] == s[1] else ""

# initialize base case
for i in range(len(s)):
for j in range(len(s)):
if i == j: dp[i][j] = 1

# construct matrix
maxlength = 1
start = len(s) - 1
end = len(s) - 1
for i in range(len(s)-1, -1, -1):
for j in range(i, len(s)):
#if not i == j:
if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1] == 1):
dp[i][j] = 1
if j - i + 1 > maxlength:
maxlength = j - i + 1
start = i
end = j

return s[start:end+1]
``````

Approach 3: Let matrix[i, j] represent whether S_i...S_j inclusive is a substring that is palindrome. With this concept, m[i, i] = 1 because a substring of length 1 is palindromic. Start from the bottom right corner (last element of string) and successively add one more element to the string. i - the outer loop - allows you to add one more element to the string. j - the inner loop - checks where the palindromes lie for the current substring. You can check whether dp[i, j] is 1 or not by checking whether the substring within it is a palindrome (dp[i+1, j-1]). if so, check if the boundary characters are the same. this means that s[i:j+1] (s_i to s_j in python form) is a palindromic substring for the current subproblem. maxlen, start, and end, store the indices of the longest palindromic substring, so by the time `i = 0 and j = n-1` start and end will hold the longest palindromic substring.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.