Longest Palindromic Subsequence - Leetcode 516 - Python

I love you neetcode

Your consistency is inspirational ❤

You don't have to run the top down dp function n times on all characters and expand outwards which is O(n^3). You can just run the dp func once with the two pointers at both ends of the string and expand in-wards instead which is O(n^2). So just the same process but going in the opposite direction and you only have to run it once so you reduce it to O(n^2) which is accepted.

Man your work is saving lives, thank you

can you please teach in c++ too

It's good that you're making videos on daily challenges 💪

i coded in java and got pass using top down dp

Thank you so much

This video has been super helpful in understanding the problem.

The recursive solution doesn't work in Java either. I have attached the dp Java solution below.

class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
int[][] dp = new int[n+1][n+1];
int res = 0;

for (int i=0;i<n;i++)
for (int j=n-1;j>i-1;j--)
{
if ( s.charAt(i) == s.charAt(j) ) {
if ( i == j )
dp[i][j] = 1;
else
dp[i][j] = 2;

if ( i - 1 >=0 )
dp[i][j] += dp[i-1][j+1];
}
else {
dp[i][j] = dp[i][j+1];
if ( i - 1 >= 0 )
dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
}
res = Math.max(res,dp[i][j]);
}
return res;
}
}

lets write some neetcode today!

when using 2 dimension array instead of a hashmap , all may tests case are passing with the same code (recursion + memo)- Integer [][] map = new Integer [1001][1001] , the constraints are too small

wow, 18 mins of explaining everything except for the required solution.

Excellent explanation. Very helpful!

Not passing in JavaScript either =(

DFS version in JS:

var longestPalindromeSubseq = function (s) {
const cache = new Map();

function dfs(L, R) {
if (L > R) return 0;
if (L === R) return 1;

const key = `${L},${R}`;
if (cache.has(key))
return cache.get(key);

let length = 0;
if (s[L] === s[R]) {
length = 2 + dfs(L + 1, R - 1);
} else {
length = Math.max(dfs(L + 1, R), dfs(L, R - 1));
}

cache.set(key, length);
return length;
}

return dfs(0, s.length - 1);
};

possible solution


from functools import lru_cache

class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
@lru_cache(None)
def dp(l, r):
if l==r:
return 1
if l>r:
return 0
if s[l]==s[r]:
return 2 + dp(l+1,r-1)
else:
return max(dp(l+1,r), dp(l,r-1))


return dp(0,len(s)-1)

I did DP for this !

Yeah I think you made a mistake here. You're recursive algorithm in n^3 not n^2. Starting with 2 pointers one at the beginning and one at the end will give you n^2. Same idea but go inwards instead of outwards.

these questions are nothing but memorization and anyone who says otherwise is a complete liar.

This was an amazing walk through. Just watching this is pleasure. Thank you so much for your hard work with these videos 🙏

What you said at the end of the video made me feel better. I arrived at pretty much exactly the same solution as you and got memory exceeded result even though all cases passed.

My god thanks @NeetCodeIO your explanations are awesome, even doing DSA courses they can't cover what you have done with your content, thanks!

Tried brute force method using c++ : time limit exceeded. My experience has been that the language doesn't really help with the time limit exceed scenarios, if it exceeds in python, there's mostly no way it'll pass in c++ (for leetcode stuff).

Serious competitive programming scenarios must be different though, I've heard that's very language sensitive.

class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
memo = [[0] * n for _ in range(n)]

def lps(left: int, right: int) -> int:
if left > right:
return 0
if left == right:
return 1
if memo[left][right] != 0:
return memo[left][right]

if s[left] == s[right]:
memo[left][right] = 2 + lps(left + 1, right - 1)
else:
memo[left][right] = max(lps(left + 1, right), lps(left, right - 1))

return memo[left][right]

return lps(0, n - 1)

Fantastic explanation