"Time Limit Exceeded" on LeetCode's Longest Palindromic Subsequence question

Question

I'm trying to solve this problem on LeetCode, which reads:

Following the most upvoted Java solution, I came up with the following memoized solution:

import functools


class Solution:
    def longestPalindromeSubseq(self, s):
        return longest_palindromic_subsequence(s)


@functools.lru_cache(maxsize=None)
def longest_palindromic_subsequence(s):
    if not s:
        return 0
    if len(s) == 1:
        return 1
    if s[0] == s[-1]:
        return 2 + longest_palindromic_subsequence(s[1:-1])
    return max(
        longest_palindromic_subsequence(s[0:-1]),
        longest_palindromic_subsequence(s[1:]))

The problem is that the time limit is exceeded for an input string which appears to have many repeated characters:

As I understand from the cited discussion, without the functools.lru_cache, the time complexity of this algorithm is O(2^N) because, at each reduction of the string length by one character, two recursive calls are made.

However, the discussion states that the memoized solution is O(N^2), which shouldn't exceed the time limit. I don't really see how memoization reduces the time complexity, however, and it doesn't seem to be the case here.

What further puzzles me is that if the solution consists of many repeated characters, it should actually run in O(N) time since each time the first and last characters are the same, only one recursive call is made.

Can someone explain to me why this test is failing?

Answer 1

String slicing in Python is O(n) (n being the length of the slice) while java's substring is O(1) as it merely creates a view on the same underlying char[]. You can take the slices out of the equation, however, by simply operating on the same string with two moving indexes. Moreover, you can move indexes past blocks of identical letters when first and last are not the same:

@functools.lru_cache(maxsize=None)
def longest_palindromic_subsequence(s, start=None, end=None):
    if start is None:
        start = 0
    if end is None:
        end = len(s) - 1
    if end < start:
        return 0
    if end == start:
        return 1
    if s[start] == s[end]:
        return 2 + longest_palindromic_subsequence(s, start+1, end-1)

    # you can move indexes until you meet a different letter!
    start_ = start
    end_ = end
    while s[start_] == s[start]: 
        start_ += 1
    while s[end_] == s[end]: 
        end_ -= 1

    return max(
        longest_palindromic_subsequence(s, start, end_),
        longest_palindromic_subsequence(s, start_, end))

Memoizaton should help significantly. Take input "abcde". In the return max(...) part, eventually two recursive calls will be made for "bcd", and even more calls for the further embedded substrings.