DP - 9: Longest Palindrome Subsequence

[@CodingSimplified]

At 28:08, in lpsBottomUp function, after initializing array, add following to make all values of diagonal to 1:
for (int i = 0; i < str.length(); i++) {
arr[i][i] = 1;
}
- I've corrected in Source code: thecodingsimplified.com/longest-palindromic-subsequence/

[@rohitpawar4096]

int palan(String s,int i,int j,int dp[][]){
if(i>j)
return 0;
if(i==j){
return dp[i][j]= 1;
}
if(dp[i][j]!=-1){
return dp[i][j];
}
if(s.charAt(i)==s.charAt(j)){
return dp[i][j]= 2+palan(s,i+1,j-1,dp);
}

int a=palan(s,i+1,j,dp);
int b=palan(s,i,j-1,dp);
return dp[i][j]=Math.max(a,b);
}
thats my code for Lps for number problem is that's i want to generate palindrom string using 2d dp array can you do it plz any other can do then comment the code.

[@tabeebyeamin9002]

Best explanation of this problem I could find!

[@CodingSimplified]

Thanks for your nice feedback. Keep Watching

[@tirupatirao7521]

Thank you very much sir, This is very helpful and please never stop your teaching, it will help so many people

[@CodingSimplified]

Thanks for your nice feedback. Keep Watching.

[@sanjogpanda2597]

Really helpful for java students. Kudos to your great work!

[@CodingSimplified]

Thanks for your nice feedback. Keep watching out other videos as well.

[@user-tq6nl1nd7i]

Hi,
The Topdown approach has failed some of the test cases, below is the one of the test cases
tkjprepggxrpnrvystmwcysyycqpevikeffmznimkkasvwsrenzkycxfxtlsgypsfadpooefxzbcoejuvpvaboygpoeylfpbnpljvrvipyamyehwqnqrqpmxujjloovaowuxwhmsncbxcoksfzkvatxdknlyjyhfixjswnkkufnuxxzrzbmnmgqooketlyhnkoaugzqrcddiuteiojwayyzpvscmpsajlfvgubfaaovlzylntrkdcpwsrtesjwhdizcobzcnfwlqijtvdwvxhrcbldvgylwgbusbmborxtlhcsmpxohgmgnkeufdxotogbgxpeyanfetcu
Code's output is: 108
It's Correct output is: 107
Thank you very much for the explanation!!

[@barunsarraf8863]

Thanks a lot. This question was hitting me from the last week. Thanks a lot

[@CodingSimplified]

Glad it was helpful!

[@omerl6415]

Very well explained. Helped me a lot, thank you!

[@CodingSimplified]

Thanks. Keep Watching.

[@tirupatirao7521]

I would have visited this channel before I wasted my interview preparation time by looking ambiguous lectures from other sources, as I am not getting the core of DP, Greedy, recursion etc..

[@CodingSimplified]

Thanks for nice words. Glad you liked content & channel. Keep Watching.

[@pinkylover911]

Thanks for the great explanation

[@CodingSimplified]

Thanks for your nice feedback. Keep Watching.

[@y7klixx]

The video was very helpful, thank you :)

[@CodingSimplified]

Thanks for your nice feedback. Keep Watching.

[@commando8822]

Great explanation!!

[@CodingSimplified]

Thanks for your nice feedback. Keep Watching.

[@divanshmahajan1769]

reverse the string and find lcs with original string..how does this soln work??

[@adarshgoyal5890]

Thank uu sir for this solution

[@CodingSimplified]

Thanks Adarsh for your feedback. Keep Watching.

[@y.ashoknaidu5787]

Well explained sir, ur great sir

[@CodingSimplified]

Thanks for your nice feedback. Keep Watching.

[@TheRajmoney]

Excellent, i like the explanation and different approaches. However, how do you print the string efficiently? I see alot of videos miss out on this part.

[@CodingSimplified]

Hi, I didn't get the question. Which String you're mentioning here. Could you please elaborate it, so that I can check it.

[@TheRajmoney]

@@CodingSimplified how do you print the solution in string rather than returning just the length.

[@TheRajmoney]

If longest palindromic subsequence is aba,
How do we print that string from the table rather than returning just 3.

[@surajgrandhi6742]

www.geeksforgeeks.org/print-longest-palindromic-subsequence/ you can see that here

[@dheerajck3881]

why you add +2 if they are equal on bottum up approach
for string abba
longest substring is 4
but using this approach we initialize to 1 and coninue so adding 2 to this will.not give 4
Could you reply on this

[@AyushKumar-vh7pg]

Sir why are we beginning the loop in bottom-up approach from end i didn't get that part

[@CodingSimplified]

You can even start from top, if you start from top, it'll fill left diagonal side. There's no specific reason. Just that we want to cover basic to complete string, so any one of diagonal you need to fill. Left or right diagonal side.

[@arepallipriyanka3737]

String is not printing how to print palindrome
string?

[@yasharthgupta9002]

class Solution {
public String solve(String finalstr,int start,int end,String dp[][]){
if(start==end)
return String.valueOf(finalstr.charAt(start));

if(start>end)
return "";
if(dp[start][end]!=null)
return dp[start][end];
if(finalstr.charAt(start)==finalstr.charAt(end))
return finalstr.charAt(start)+solve(finalstr,start+1,end-1,dp)+finalstr.charAt(end);

String retvalue1 = solve(finalstr,start+1,end,dp);
String retvalue2 = solve(finalstr,start,end-1,dp);

if(retvalue1.length()>retvalue2.length()){
dp[start][end] = retvalue1;
return retvalue1;
}

else{
dp[start][end] = retvalue2;
return retvalue2;
}
}

public int longestPalindromeSubseq(String s) {
String dp[][] = new String[s.length()+1][s.length()+1];
String ans = solve(s,0,s.length()-1,dp);
return ans.length();
}
}

[@urmyjudgementalfrndcinemah6748]

What is DP sir please reply

[@CodingSimplified]

DP - Dynamic Programming is technique to solve coding problems.