Longest Palindromic Subsequence

hello friends my name is Tushar and today we are going to look at the question longest palindromic subsequence so the question is given a string a G B D be a find the longest palindromic subsequence inside this frame so in this case an honest palindromic subsequence is of length five and the string is subsequences a b d be a a b d be a notice how this is a palindrome and notice how this is not continuous in the original string if you remember this question is different from longest palindromic substring where the where the characters need should be continuous so the longest palindromic substring here will be b DM b whose length is 3 but we are looking for longest palindromic subsequence whose length is 5 so the characters need not be continuously in the original string so how do we solve this problem yes we will use java programming to solve this question so i have a two-dimensional matrix here of the same length as original strength 5 6 cross 6 matrix here so now we are going to fill up this matrix and we'll have the final result right here so let's see how this works let's start with L is equal to 1 when I say L is equal to 1 when I'm just considering one character at a time so if I only had a string of length 1 and that string was a what is the longest palindromic subsequence I can have of which is of length once and that goes at 0 and 0 if I had a string of character length 1 and that string was G the longest palindromic subsequence I could have is of length 1 so the 22 is 1 1 1 1 again 5 and 5 means a string starts at 5 and ends at 5 and this is the character and the longest palindromic subsequence it will be of length 1 so if let's move on to let's - so now I'm considering two characters at a time the original string so if I hide this train and I considered these two characters together what is the longest palindromic subsequence I can have between a and G since these guys are not same then on expanding the subsequence here will be of length 1 again so 0 & 1 0 & 1 this will fill up this particular cell so that's 1 now let's have let's consider these two guys together again since they are not same we fill 1 & 2 with 1 1 & 2 is 1 B and D are not same so 2 & 3 is 1 what means is that if between 2 & 3 the longest better knowing subsequence you can get is of length 1 similarly for 3 & 4 is not same so will be again 3 & 4 will be filled with 1 & 4 & 5 will be filled with 1 all right let's move L is equal to 3 so basically now we are looking three characters at a time in the original string here again a is not same as B so the longest palindromic subsequence here will be the max of this - or this - so let's see a G and B so the longest palindromic subsequence will either be the max of these two whatever is the longest but in a subsequence here or this - in this case both of them are 1 so it doesn't matter so 0 to 2 is max of these 2 which is 1 all right now let's see now we will consider this 3 again they are not same so the max will be max of either 1 2 & 2 3 so we are filling 1 2 3 so this will be max of this or this that's 1 similarly 2 - 4 now here they are same let's see how it's different now this B is same as this B so the max the longest palindromic subsequence will be of length 2 this 2 is coming from these 2 B's plus the longest value movie subsequence at point 8 point 3 & 3 which is 3 and 3 is 1 so the lon 3 & 3 is 1 so 1 so that's 3 so when B when 24-hour same so the longest palindromic subsequence will be 1 plus 2 so 3 now let's have DNA since DNA are different longest but I know P sub sequence will be max of this or there's a 1 max of 1 or 1 so that's so 3 & 5 101 is 1 all right now I will have L is equal to 4 okay so now we start again from zero to three since a and D are not same the longest palindromic subsequence will is a max of 0 to 2 or 1 to 3 so 0 to 3 are the max of these two so again it's 1 let's move on since G and B are not same again the max here 1 to 4 will be max of this or this so max of this or this so 3 so max of this part or this part now will have these two guys so since these guys are not same again so 2 & 5 will be max of this world then stood three nights of this part of this part so three all right let's move L is equal to 5 so we are considering this 5 again a is not same as B so the max the longest bedroom subsequent between A to B will be max of this size for this size so basically here max of this or this so that's 3 now let's have this between this since these guys are different the longest by the Ruby subsequence between 1 to 5 will be max of this or this so it doesn't matter any of them to 3 all right now let's look at L is 6 so now we are considering the entire spring since they are same the longest pattern will be subsequence will be 2 this 2 is coming from good that is plus the longest between 1 & 4 so long as between 1 & 4 is 3 plus this 2 so 5 so if so if we had a string a B a G B D be a the longest pendulum subsequence will be of length five if someone asked you what is that longest by the river subsequence so you can get this answer from looking at this matrix so we'll start from here we know that this find is coming from this guy so whatever is at zero and whatever is at five will be the answer so as a is at the 0 and a is at five so they are in the answer and we move to 3 this 3 here is coming from here so we move down this 3 here again is coming from 1 plus 2 so we know that 2 & 4 is the answer so 2 is B 4 is also B and we move here this one is just coming from here so we know that 3 & 3 is in the answer which is B which is d so the longest palindromic subsequence will be a b d be a of the in the original strain let me quickly write a formula for this one if a put off time is equally put in put off gee key of I G is the - T of I minus 1 I plus 1 J minus 2 1 plus 2 so if they are saying we look diagonally across else T of I J is equal to T off max of T of I plus 1 J or T of I J minus 1 if you want the full goal for this solution go to my github link github.com mission piece interview wiki and if you want to check out similar questions go to my youtube channel youtube.com user to charoite 2535 thanks for watching this video

Channel: Tushar Roy - Coding Made Simple

Views: 271,110

Keywords: dynamic programming, interiview, coding, longest palindromic subsequence, longest palindromic subsequence dynamic programming, computer science, palindromic subsequence

Id: _nCsPn7_OgI

Length: 9min 18sec (558 seconds)

Published: Sat Mar 14 2015