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]:
memo_set.add(indices)
return True
return False
if s[i] == s[j] and (i + 1, j - 1) in memo_set:
memo_set.add((i, j))
return True
return False
```

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?