DP Python (explained in detail) TLE on test case "ddd..."

• Hello! I saw many posts about Time Limit Exceeded with a Dynamic Programming solution, so I was wondering if I could get some help with mine. High level overview (rough) of my solution is:

for substring lengths 1 to n (where n is the length of the given string),
-- for all substrings of this length
---- check if the substring is a palindrome (using string indices, otherwise slicing the string will make the check linear time). If it is, store the indices in a set ("memoize") so that when we're checking bigger substrings on next iterations, we can check if the smaller ones are in the set in constant time.
return the longest substring

And here it is in code:

``````class Solution(object):
def longestPalindrome(self, s):
longest = (0, 0)
memo = set()
for substring_length in xrange(1, len(s) + 1): # start with smaller substrings and memoize
for i in xrange(0, len(s) - substring_length + 1): # e.g. for s = 'abcde' and substring_length = 2, i goes from
sub_indices = (i, i + substring_length - 1) #  0 to 3 and sub_indices will be (0, 1), (1, 2) ...
if self.is_palindrome(sub_indices, memo, s):
longest = sub_indices
return s[longest[0]:longest[1] + 1]

def is_palindrome(self, indices, memo_set, s):
i, j = indices
if j - i <= 1: # 2 or less characters
if s[i] == s[j]:
I have 2 for loops and my `is_palindrome` method clearly takes constant time, so this solution seems to be O(N^2). Am I missing something? If not, why does this fail on the 'ddd...' test case?