# Longest Palindrome Substring: Where is the dynamic programming? [closed]

In this LeetCode problem, Longest Palindromic Substring, it is listed under Dynamic Programming for Google interview preparation. My understanding of dynamic programming is roughly "recursion + memoization + guessing." In the Python solution to this answer below it is not clear to me where the dynamic programming is if it exists at all. This is Approach 4 under solutions (translated from Java to Python). Approach 3 references dynamic programming but no solution is given.

Is there any dynamic programming going on here? Or is this just a solution to solve the problem in O(1) space, where the dynamic programming solution requires O(n^2) space?

This algorithm technically has a time complexity of O(n^2) right? Is this the best we could reasonably be expected to do in an interview?

class Solution:
def longestPalindrome(self, s):
res = ""
for i in range(len(s)):
# odd case, like "aba"
tmp = self.helper(s, i, i)
if len(tmp) > len(res):
res = tmp
# even case, like "abba"
tmp = self.helper(s, i, i+1)
if len(tmp) > len(res):
res = tmp
return res

# get the longest palindrome, l, r are the middle indexes
# from inner to outer
def helper(self, s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r]

• Which website should this be included on? – Scott Skiles May 20 at 16:29