Leetcode memory optimisation - Longest Palindromic Substring

Question

I've done a lot of Leetcode questions lately. When I failed to do some question, I've always knew why, but not this time - question 5. Longest Palindromic Substring:

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"

Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

My code:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def is_palindrom(word):
            for i,letter in enumerate(word):
                if letter != word[-i-1]:
                    return False
            return True
        out = ""
        checked_words = set()
        def dp(word):
            nonlocal out
            if len(word)>len(out) and word not in checked_words:
                checked_words.add(word)
                if is_palindrom(word) and len(word)>len(out):
                    out = word
                dp(word[:-1])
                dp(word[1:])
        dp(s)
        return out

Issue: Memory Limit Exceeded on imput: s = "rgczcpratwyqxaszbuwwcadruayhasynuxnakpmsyhxzlnxmdtsqqlmwnbxvmgvllafrpmlfuqpbhjddmhmbcgmlyeypkfpreddyencsdmgxysctpubvgeedhurvizgqxclhpfrvxggrowaynrtuwvvvwnqlowdihtrdzjffrgoeqivnprdnpvfjuhycpfydjcpfcnkpyujljiesmuxhtizzvwhvpqylvcirwqsmpptyhcqybstsfgjadicwzycswwmpluvzqdvnhkcofptqrzgjqtbvbdxylrylinspncrkxclykccbwridpqckstxdjawvziucrswpsfmisqiozworibeycuarcidbljslwbalcemgymnsxfziattdylrulwrybzztoxhevsdnvvljfzzrgcmagshucoalfiuapgzpqgjjgqsmcvtdsvehewrvtkeqwgmatqdpwlayjcxcavjmgpdyklrjcqvxjqbjucfubgmgpkfdxznkhcejscymuildfnuxwmuklntnyycdcscioimenaeohgpbcpogyifcsatfxeslstkjclauqmywacizyapxlgtcchlxkvygzeucwalhvhbwkvbceqajstxzzppcxoanhyfkgwaelsfdeeviqogjpresnoacegfeejyychabkhszcokdxpaqrprwfdahjqkfptwpeykgumyemgkccynxuvbdpjlrbgqtcqulxodurugofuwzudnhgxdrbbxtrvdnlodyhsifvyspejenpdckevzqrexplpcqtwtxlimfrsjumiygqeemhihcxyngsemcolrnlyhqlbqbcestadoxtrdvcgucntjnfavylip"

I've tested my solution on my local setup and solution don't require a lot of RAM memory - about 128MB (tested with process.memory_info().rss), 16MB just for checked_words set (tested with sys.getsizeof()). What could be an issue? How to identify which part of program is causing memory problems?

Answer 1

Your code is too inefficient; there is no need to run a linear loop for every single possible substring to check if it is a palindrome. Since the maximum string length for this problem is only 1000, we can use a simple O(|s|^2) dynamic programming solution that makes use of previous computed results.

Let is_palindrome[l][r] indicate whether the substring from index l to r (inclusive) is a palindrome. First, we initialize this table for all length 1 and 2 palindromes. For substrings of length at least 3 (r - l > 2), is_palindrome[l][r] will be true iff if the characters at index l and r match and the substring formed by cutting off one character from each end is also a palindrome (i.e. is_palindrome[i + 1][r - 1] is true).

class Solution:
    def longestPalindrome(self, s: str) -> str:
        is_palindrome = [[False] * len(s) for _ in s]
        ans = (0,1)
        for i in range(len(s)): is_palindrome[i][i] = True
        for i in range(len(s) - 1): 
            if s[i] == s[i + 1]:
                is_palindrome[i][i + 1] = True
                ans = (i,i+2)
        for l in range(3, len(s) + 1):
            for i in range(0, len(s) - l + 1):
                if s[i] == s[i + l - 1] and is_palindrome[i + 1][i + l - 2]:
                    is_palindrome[i][i + l - 1] = True
                    ans = (i,i+l)
        return s[slice(*ans)]

Note that there are also solutions that solve this problem in O(|s|) time, but that is not necessary for this question.

Answer 2

Leetcode's reporting of memory usage is bizarre. According to that platform, my solution uses >16MB

Whilst it is true that new lists are being constructed (due to slicing), those lists are transient and therefore consume a minimal amount of memory - i.e., they're constructed, used in a comparison and then (implicitly) discarded. The problem description states that the input string will be <=1000 characters

class Solution:
    def longestPalindrome(self, s: str) -> str:

        def ispalindrome(s):
            return s == s[::-1]
        
        if len(s) < 2:
            return s
        
        start = 0
        size = 1

        for i in range(1, len(s)):
            left = i - size

            if left >= 1 and ispalindrome(s[left-1:i+1]):
                size += 2
                start = left - 1
            else:
                if ispalindrome(s[left:i+1]):
                    size += 1
                    start = left

        return s[start:start+size]