# How do I optimize memoization in order to find longest palindromic substring?

I want to find the longest palindromic substring using dynamic programming in Python3. The strings can be as large as this string.

I have seen other questions on this problem that successfully solve it but I am unable to improve my own code following their strategy.

This, approach 3 is the strategy that I want to implement. Even then, my code is not time-efficient.

My code is:

class Solution:

def __init__(self):
self.not_pal = {}
self.pals = {}

def check_pal(self, s, i, j):
if len(s) == 0:
return False
if i == j:
return True
if i == j-1:
if s[i] == s[j]:
return True
return False
if s[i] == s[j]:
return self.check_pal(s, i+1, j-1)
return False

def longestPalindrome(self, s):
max_pal_str = ''
length = len(s)
for i in range(len(s)):
if length-i <= len(max_pal_str):
continue
for j in range(len(s)-1, -1, -1):
if self.not_pal.get(s[i: j+1]):
continue
if self.pals.get(s[i: j+1]):
continue
if len(s[i: j+1]) <= len(max_pal_str):
continue
if self.check_pal(s, i, j):
self.pals[s[i:j+1]] = 1
if len(s[i: j+1]) > len(max_pal_str):
max_pal_str = s[i: j+1]
else:
self.not_pal[s[i:j+1]] = 1
return max_pal_str



I am unable to improve this code further. I expect it to be faster than brute force codes which check all the permutations and combinations without any memoization. It is failing with TLE on Leetcode.

• Well, you succeeded in writing pretty unreadable code =) What's with all the the single-letter variable names and magic numbers?
– Mast
Oct 30, 2019 at 17:21
• @Mast I am sorry for writing bad code. i,j -> loop iterators s -> given string 1 is just any value in the dictionary(I should have used sets, right?) Is there any other friction for you to read the code? Apologies for presenting it in such a state. Oct 30, 2019 at 17:26
• To counter-balance the unclear variable names, maybe you could add more context to your question :) This way, we could help you write clearer code. Oct 30, 2019 at 19:06
• You say "The strings can be as large as this string", but which string do you mean? You also talk about "This, approach 3 is the strategy that I want to implement", but I have no idea what you mean by that. Please add a bit more detail, like the problem description and what your strategy to solve it actually is. Oct 31, 2019 at 15:25
• Does the problem on Leetcode require that your code be in a class like this?
– AMC
Nov 4, 2019 at 2:08