# Python solution with detailed explanation

• Solution

Longest Palindromic Subsequence https://leetcode.com/problems/longest-palindromic-subsequence/

Algorithm

• LPS(i,j) = LPS(i+1,j-1) + 2 ....................................................s[i] == s[j]
• LPS(i,j) = max(LPS(i,j-1), LPS(i+1,j)) ....................................s[i] != s[j]
• LPS(i,j) = 0 .....................................................................................i > j
• LPS(i,j) = 1 .....................................................................................i = j
``````from collections import defaultdict
class Solution(object):
def helper(self, i, j, s, cache):
if i > j:
return 0
elif i == j:
return 1
elif i in cache and j in cache[i]:
return cache[i][j]
elif s[i] == s[j]:
cache[i][j] = self.helper(i+1, j-1, s, cache) + 2
return cache[i][j]
else:
cache[i][j] = max(self.helper(i, j-1, s, cache), self.helper(i+1, j, s, cache))
return cache[i][j]

def longestPalindromeSubseq(self, s):
"""
:type s: str
:rtype: int
"""
cache = defaultdict(dict)
return self.helper(0, len(s)-1, s, cache)
``````

• The `cache = defaultdict(dict)` is brilliant.

I was using (i, j) tuple as the key, as the code shown below, but got Memory Limit Exceeded on the 64 / 83 test case.

``````class Solution(object):
def longestPalindromeSubseq(self, s):
def helper(i, j):
if i > j:
return 0
if i == j:
return 1
if (i, j) in cache:
return cache[(i, j)]

if s[i] == s[j]:
length = helper(i + 1, j - 1) + 2
else:
length = max(helper(i, j - 1), helper(i + 1, j))
cache[(i, j)] = length
return length

cache = {}
return helper(0, len(s) - 1)
``````

• @gabbu what is the time complexity?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.