Longest Palindromic Subsequence | Dynamic Programming | Set 12 | GeeksforGeeks

Soundtrack: TITLE1 by ARTIST1

This video is contributed by Ishant Periwal

Please Like, Comment and Share the Video among your friends.

Also, Subscribe if you haven't already! :)

[kishorebatta]

After struggling for 4 hours to understand, i found something of 4 minutes to get this clear. Thanks Geeks for Geeks.

[adamtheanalyst]

Perfectly visualized video. Showing the solution to this exercise so eloquently in 4.5 minutes is an absolute art. Love it!

[Sulerhy]

This is an absolutely perfect explanation. Tabulation is extremely difficult to imagine. I actually prefer DP memorization because it is easier to look at the code and understand the idea behind.

[pavansonty]

This can also be solved by interpreting it as variation of LCS (Longest Common Sub-sequence). Let the given string be 'str'. We reverse the string and call it 'revStr'. Now I believe LPS is nothing but LCS between 'str' & 'revStr'.

[KnowledgeAmplifier]

Without dynamic programming(JAVA):


import java.util.*;
import java.lang.Math;
import java.io.*;
class Mo
{
public static void main(String args[])throws IOException
{
BufferedReader r=new BufferedReader(new
String a=r.readLine();
int l=a.length();
LinkedList<String> ab=new LinkedList<String>();
int id=(int)Math.pow(2, l);
for(int i=0;i<id;i++)
{
String
if(er.length()!=l)
{
for(int
{
er="0"+er;
}
}
ab.add(er);
}
//System.out.println(ab);
LinkedList<String> g=new LinkedList<String>();
for(int i=0;i<ab.size();i++)
{
String t=ab.get(i);
String st="";
for(int j=0;j<t.length();j++)
{
if(t.charAt(j)=='1')
{
st=st+a.charAt(j);
}
}
//System.out.println(st);
String gs="";
for(int is=st.length()-1;is>=0;is--)
{
gs=gs+st.charAt(is);
}
if(gs.length()!=0)
{
if(gs.compareTo(st)==0)
{
g.add(gs);
}
}
}
//System.out.println(g);
String op=g.get(0);
int tr=op.length();
for(int uk=1;uk<g.size();uk++)
{
String hg=g.get(uk);
if(hg.length()>tr)
{
op=hg;
tr=hg.length();
}
}
System.out.println(tr);
}
}

[rockmanvnx]

I think most of the people here have the expectation that the question is asking for substring instead of sequences. For substring we can just simply tweak the if statement

For example, given the code, if we try something like `acba` this code might fail because of the condition:

if (i == j) then dp[i][j] = dp[i + 1][j - 1] + 2

This essentially means take the result of the middle substring without the i and j character (dp[i + 1][j - 1]) and + 2 (including character i and j). However, with acba, the middle part `cb` will be `1` and plus `2` which means 3, this is wrong.

We can simply fix by this logic:

if (i == j) and dp[i + 1][j - 1] >= length of the substring from i+1 to j - 1 then dp[i][j] = dp[i + 1][j - 1] + 2

or

if (i == j) and dp[i + 1][j - 1] >= (j - 1 - (i + 1)) + 1 then dp[i][j] = dp[i + 1][j - 1] + 2
Else we fall back to the other condition as shown in the video

Code to try out:

from typing import *

class App:
def longestPalindromeSubString(self, s: str) -> int:
dp = [[0 for _ in range(len(s))] for _ in range(len(s))]

for i in range(len(s)):
dp[i][i] = 1

for length in range(2, len(s) + 1):
start = 0
end = start + length - 1 # inclusive

while (end < len(s)):
if s[start] == s[end]:
lengthPreviousSubstring = (end - 1 - (start + 1)) + 1

if dp[start + 1][end - 1] >= lengthPreviousSubstring:
# previous substring must be palindrome
dp[start][end] = dp[start + 1][end - 1] + 2 # 2 is 2 new characters
else:
dp[start][end] = max(
dp[start + 1][end], # star + 1 -> end group
dp[start][end - 1] # start -> previous char group
)
else:
dp[start][end] = max(
dp[start + 1][end], # star + 1 -> end group
dp[start][end - 1] # start -> previous char group
)

start += 1
end = start + length - 1

return dp

[prabhathkota]

Very well explained. A picture is worth a thousand words

[FrankLi]

wow this video was top notch and made it much more clearer that even the best youtubers that explain this. The magic of visualization...with perfect synchronicity of the moving parts helps paint the clearest picture

[ven]

Wow what an amazing video. It explains better than any of the lecture driven video out there.

[Dylan]

waht i don't get is if the be in the index at 2 is say a c, wouldn't that break it and say that the longest is 3 anyway for that length string when there isn't any at all?

[rajawatlks]

Its awesome.
Thank you so much
Geeks for Geeks is helping lot of people in free of cost
May God Give lot's of blessing to them

[sahulrajhansa]

These videos are way better than the ones which are explained by the humans

[siqiliu]

The best of the best! Thousands of thanks!

[yuhangcao]

Really nice video, awesome and clearly.

[abhisheksrivastava]

I am found difficulty in understanding that why the first loop started from c1=2?
is there is some other approach available which is though simple then this??
please reply asap

[ankitpodder]

I think there is some mistake.
If input : abda
Exp output : 1
But output : 3
If(str[i] == str[j])
return 2 + rec(i+1, j-1);
It think this line of code creates some problem.

[xpzzz]

Amazing. the best demonstration of this problem i have ever seen

[stockswithgpt]

I don't think it always works, I took the code u guys have and tested it against seq = aacabdkacaa, the answer is incorrect

[deeprabasak]

Very nice explanation and representation

[shalinisharma]

Thanks for the great video, gfg🤗. I hope I will be doing such problems myself in the coming time.