Longest Common Subsequence Video: ruclips.net/video/Ua0GhsJSlWM/видео.html This problem is basically a variation of that one, so recommend understanding it.
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.
Brilliant! it can also avoid the problem of odd and even length. cache={} def dfs(l,r): if rlen(s)-1: return 0 if (l,r) in cache: return cache[(l,r)] if s[l]==s[r]: cache[(l,r)]=1+dfs(l+1,r-1) else: cache[(l,r)]=max(dfs(l+1,r),dfs(l,r-1)) return cache[(l,r)] dfs(0,len(s)-1) return max(cache.values())
@@NeetCodeIO hi i am not sure but i think that with caching its O(n^3) as their is the for loop outside which runs on each letter for even and odd and the recursion with caching is O(n^2) so total is o(n^3) and thats why it timeout
right, if you observe, this approach is essentially same as the LCS, except that the pointers now are pointing to start and end of the same string rather than starts of two different strings
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
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.
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;ii-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; } }
Longest Common Subsequence Video: ruclips.net/video/Ua0GhsJSlWM/видео.html
This problem is basically a variation of that one, so recommend understanding it.
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.
Good point! But I believe even running it n times, with caching is still O(n^2) - correct me if i'm wrong
Brilliant! it can also avoid the problem of odd and even length.
cache={}
def dfs(l,r):
if rlen(s)-1:
return 0
if (l,r) in cache:
return cache[(l,r)]
if s[l]==s[r]:
cache[(l,r)]=1+dfs(l+1,r-1)
else:
cache[(l,r)]=max(dfs(l+1,r),dfs(l,r-1))
return cache[(l,r)]
dfs(0,len(s)-1)
return max(cache.values())
@@NeetCodeIO hi i am not sure but i think that with caching its O(n^3) as their is the for loop outside which runs on each letter for even and odd and the recursion with caching is O(n^2) so total is o(n^3) and thats why it timeout
@@sidazhong2019 could you explain why we are letting the l,r pointers to overlap so the r would become less than the l pointer ?
right, if you observe, this approach is essentially same as the LCS, except that the pointers now are pointing to start and end of the same string rather than starts of two different strings
Man your work is saving lives, thank you
Your consistency is inspirational ❤
It's good that you're making videos on daily challenges 💪
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
lets write some neetcode today!
I love you neetcode
holy fuck this is juda from the discord
@@julianelmasry9556 hi!
Love u
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.
Excellent explanation. Very helpful!
I did DP for this !
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)
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;ii-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;
}
}
Using this solution is also fine and better no?
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);
};
this is the easiest and intuitive answer I think
Thank you so much
1:42 "aya" is also a palindrome?
i coded in java and got pass using top down dp
Not passing in JavaScript either =(
these questions are nothing but memorization and anyone who says otherwise is a complete liar.
can you please teach in c++ too
wow, 18 mins of explaining everything except for the required solution.