Longest Palindromic Subsequence - Leetcode 516 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem longest palindromic subsequence we're given a string s and we want to return the length of the longest palindromic subsequence to quickly review a subsequence of a string like b b a b is basically a sequence of characters in this string where we are allowed to skip some characters like we could skip this a if we wanted to the resulting string then is just BBB is this a palindrome yes because a palindrome basically means the string when it's been reversed take this and reverse it it's still going to be BBB well a fourth B and these two happen to be equal so this is a palindromic subsequence of the original string and it happens to be the longest one the length of it is four so there's actually two solutions to this problem but before I get into it I want to say that I highly recommend solving the longest common subsequence problem before attempting this one this one becomes pretty easy after you understand this one and this is one of the most popular interview questions I have a video on it that I'll link below if you want to check it out but it's funny that this algorithm actually can exactly solve this problem it's a pretty clever solution so I'll explain to you how it works the LCS algorithm takes two strings such as a a b and maybe x a y a and with these two strings we find the length of the longest common subsequence you can kind of tell what it is just by looking at it if we take the first two A's from this string and we take the two A's from this string they are the same string two A's right so the length of it is going to be two we can actually be really clever with this problem and apply this algorithm to this problem even though there's just a single input string basically we would take the input string that would be one parameter and we would also take the reverse of this string which would be b a b b b and then run LCS on these two strings Not only would it find the length of the longest common subsequence but it guarantees that the subsequence also happens to be a palindrome because we reversed the input string so it must be a palindrome let me explain exactly why first so we know with this string this happens to be the result Four B's in this example it's pretty obvious that LCS is gonna find that string four consecutive B's is the longest common subsequence between these two strings but is it guaranteed that the longest common subsequence is always going to be a palindrome why is that the case well what if we had a string like this a a b and then some other characters x y z whatever and then we took the reverse of this string b a a a is it ever possible that the LCS algorithm is gonna find a subsequence that is not a palindrome is it possible that if we pass this string and the reverse of this string into our LCS function it's going to identify this as the longest common subsequence which is of length 3 which in this case clearly this is not a palindrome is that ever gonna happen my answer to you is no it's obvious when you look closely if we ever find a string over here and we also find the reverse of the string somewhere else in the input string can't we take the concatenation of these two strings which is a a b and then here b a a and look at this it's a palindrome so if we ever find a string over here that matches a string over here and this string happens to not be a palindrome doesn't matter we can combine them and make a palindrome anyway so I pretty much proved to to you that if we pass a string and the reverse of it into LCS we're always going to get a palindrome as the result and if we're always going to get a palindrome as a result clearly the LCS algorithm is going to find the longest palindrome by definition that's what LCS stands for longest common subsequence so literally if you can code this algorithm up you can solve this problem the time complexity of LCS if you code it up efficiently is going to be n times M where these are the lengths of the two input strings but clearly in this case both input strings are going to be of the same length so we can say the time complexity is Big O of N squared where n is the size of this string so I'm going to quickly show you the code even though it's pretty much just going to be this algorithm but then I'm going to show you the more intuitive way to solve this problem because to be honest I was not able to come up with this clever approach when I first solved this problem I came up with a different approach but it's similar to LCS so very quickly this is the longest common subsequence algorithm I pretty much just copy and pasted it because you can literally take your solution from a different lead code problem and then all you have to do is call it like this we're calling the longest common subsequence passing in the input string s and for the second parameter we're passing in the reverse of the string s this is how you do it in Python you can do it differently in other languages but this is literally how you can solve the problem I'll run it quickly to prove it to you and as you can see it does work now if you want a deeper understanding of this algorithm I have a full video on it so you can check that out below Now quickly let me show you a different way to solve this problem it's also going to be a dynamic programming approach and we're going to borrow a lot from LCS we're going to look at this input example but I'll also mention that we're also going to borrow ideas from leak code problem five I think it's longest palindromic substring and the idea is that to find the longest palindrome from a string efficiently instead of starting from left to right and looking at this string and then looking at this string and this string that's going to be very brute force and we're going to end up getting N squared substrings and then for each string we have to check if it's a pound drum or not that's going to be n cubed there is a more efficient way to do it we start at each character from here we start expanding outwardly because it's more efficient to do it that way because for each position we can only expand up to n characters and we have only n positions here anyway so we eliminate some of the repeated work because what we can do from a character like B here in the middle we can look at its two Neighbors First of all we know that this string B itself is a palindrome any single character is a palindrome but now when we look at the neighbors this B and this a these do not match each other if we want this string to be a palindrome these neighbors must match each other clearly they don't in this case so we can't make a longer palindrome centered around this position so we can pretty much give up then we might want to try over here we try expanding left and right these two neighbors are the same so this is a palindrome now we might try to expand again but there are no more characters left over here there are some over here clearly we can't expand this palindrome that's centered around this position if we start at each individual character and try to expand outward we're only going to get palindromes of odd length if we also want to get the Palm Drums of even length we start at each pair of characters like now we check the pound drums centered around these two characters and we try to expand outwardly but before we even do that we have to make sure that these two characters are equal and in this case they are but we can't expand any further next we might want to try this position and then we'd look at the two neighbors b and a these do not match each other so we can't get a longer palindromic substring so centered around this position but so far I've only been talking about sub strings this problem is not about substrings it's a bit more complicated we are talking about subsequences here so how do we get longest common subsequences because ultimately we know our result is going to be this the Four B's and yes it's going to be centered around this position so how would we get the solution well we would look at our neighbors b and a they're not the same so what do we do do we just give up looking from this position no because with subsequences we are allowed to skip characters so what we might say now is let's consider skipping this character or let's consider skipping this character we don't know which one is going to lead us to the result so we have to try both ways we have to sort of Brute Force this algorithm so to Brute Force this algorithm first I'm going to give an index to each of these values use and let's say we're starting here with our decision tree we have a pointer let's say I is going to be at index one J is going to be at index two so that's how I'm going to represent our decision tree we're at this sub string so this is kind of the range that we are considering so far it doesn't necessarily mean we are including every single character in The Range as I'm going to show you in just a second but now we are gonna try to expand outward and the reason we're expanding outward is because we found that these two characters do match each other and I'm going to show you what we're going to do when these characters don't match each other but for now we can go ahead and expand the eye this way and the J in the other direction we don't even have multiple decisions here we just have a single decision because we're being greedy we can include both of these so that's what we're going to do so now our eye pointer is going to be zero our J pointer is going to be three here though we find that the characters b and a do not match each other so we don't give up searching in this direction though we're gonna try to skip both characters in the case that we end up skipping the B character what we would say is take our eye pointer and decrement it one more time clearly when we try to do that we're gonna end up here negative one three that means our eye pointer went out of bounds so we can't do anything anymore at this point we do have to give up but there was another opportunity for us where our J pointer which is at index three here is going to be shifted to the right one more time it's going to be four we're gonna have zero four and at this point we see that this character at index 4 and the character at index zero I know I have it crossed out over here but they're both B's so they do match each other by the time we get here we find that the longest palindromic subsequence so far is gonna be of length four I think it's clear that this approach this Brute Force approach will lead us to the correct solution but what's the time complexity and how can we make this more efficient I think that's best explained by taking a look at the code so that's what I'm going to do right now but we can see that clearly this decision tree is going to be exponential in the worst case the length of the string is n roughly the height will be the same thing and we are in the worst case branching twice at each node so in the worst case the size of this tree is going to be 2 to the power of n but I'm going to show you how we can use memoization a dynamic programming technique to make this more efficient and actually be N squared let's do that now as I mentioned we are going to do this recursively so I'm going to create a method called DFS and we're going to have two parameters the index I and the index J or you could say left and right l r I think that might be more descriptive but I'll stick with this because that's what I used in the drawing explanation first let's start with the base case which was kind of obvious from the drawing explanation but it's going to be when one of these pointers goes out of bounds if I is too small because I is our left pointer if it's less than zero or if J is too big meaning it's equal to the length of s in that case we would say the longest palindromic subsequence is zero of the subsequent characters next we have a couple cases one what if the characters in these two positions match each other if the character at pointer I is equal to the character at pointer J that means the characters match in the other case that means the characters don't match I think this case is a bit more interesting so I'm going to start with that but this is the one where we have to branch in both directions we have to make a DFS call where we decrement our I pointer we shift it to the left while keeping the J pointer the same but we also have a case where we do the opposite we keep I the same but we increment our J pointer we shift it towards the right we don't know which one of these is going going to result in a maximum palindromic subsequence so we try both of them and we take the max of their result so that's what I'm going to do now before I fill in this case I'm going to show you how we're actually going to be using this DFS this is going to return the length of the longest palindromic subsequence and I'm going to show you quickly how we're going to use it we're going to go through every position in our input string s so we need the length of s and for each of these positions we're going to call our DFS where I is both going to be the left character and the right character this is where we're calculating the odd length palindromic subsequences but we know we also have to calculate even length palindromic subsequences which we can do like this where we have I but the second character is going to be I plus one this is the even length palindromic subsequences it still guarantees though that we call our DF FS method I think 2 times n times so still not too bad it won't change the overall time complexity that we are calling this twice so now that we know that it kind of informs us how to handle this if statement because it's possible that I and J could be at the same character or they could be at different characters this is going to inform how we calculate the length of this palindromic subsequence because if I is equal to J then we want length to be assigned to one we have one character that is a palindrome but if they are not at the same character then we want this to be assigned to two we want the length to be two because we found two different characters that are the same so we filled in most of the skeleton of this DFS well here I guess one thing that's missing is we now want to continue to do DFS but in this case we're going to shift both of the pointers we're going to decrement I and we're going to increment J because we found two characters that match so we can shift both pointers and we're going to add the result of this DFS to the length that we just computed it could be one or it could be two and this is what our result would be adding these two together even though I'm not returning anything yet and I'm not really calculating the entire result this is pretty much the Brute Force solution we're going to be doing a lot of repeated work the total number of possible combinations of I and J that could be passed into this DFS is N squared because this could have n possible values this could have n possible values so it's N squared clearly within the loop we're only doing o of one operations other than the recursive calls so if we can cache the repeated work in a cache which I'm going to use a hash map but you could also use a two-dimensional array if we can cache the repeated work we can get the time complexity to be N squared so that's what I'm going to do first things first our second base case is going to be if this has already been computed if I and J happens to already be in our cache then we're going to return the value that is stored in the cache so let's do that and also anytime we compute a result we want it to be stored inside the cache that's kind of the whole point so I'm going to copy this and here where we are Computing the result if the characters match we want to assign that to this position in the cache in the else case we want to do the same thing let's assign this to the cache and our ultimate return value is going to be what we ended up storing in the cache and the way that I'm calculating this we could use the return values from these method calls to maintain like a max value but it's a little bit easier to just say return the cash dot values so this will be the entire list of values stored in our cache and we want to return the maximum one so we can do it just like this I'll run the code to make sure that it works okay well the code does work but it is giving time limit exceeded even though this is the same Big O time complexity as the first solution that I showed you so that's unfortunate I'm pretty sure that this would get accepted in a language like C plus plus if you coded it like the exact same way you can let me know in the comments but this is unfortunate it's possible that if we coded this up without recursion it would pass on leak code and I'll quickly copy and paste the code for that but I think this video has dragged on long enough I think the most important thing is understanding the solution and how to arrive at it not getting it passed on leak code so I'll run this really quickly to see if this will work okay I guess it does that's unfortunate but I try not to waste too much time on what leak code deems as like an acceptable solution or not even though both of these are the same Big O time complexity so I'll leave it at that you can let me know if you have any comments below if you found this helpful please like And subscribe if you're preparing for coding interviews check out neatco.io it has a ton of free resource is to help you prepare thanks for watching and hopefully I'll see you pretty soon