Unique Length 3 Palindromic Subsequences - Leetcode 1930 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. And today's video actually I've already recorded before today's problem. And I was looking at it and seeing if it was good enough. And I have to say for a video that I made over 3 years ago back when I was still unemployed. This one is actually not too bad. I'm going to re-record it though because I think I could probably explain the exact same thing in about like half the time. Let's see if I turn out to be correct or not. But uh here goes. unique length three palendromeic substrings. So the idea is we're given an input string of lowercase a through z character. So for this input string example we have a a b c a and that's the only parameter we're given a string. And so what we want to do is count how many length three palindromes are there. What's a palenrome? Basically something that is read the same forward and back. So like a a a is a palendrome. ABA AA is a palendrome. ABC is not a palendrome. But we're not looking for substrings this time. We are looking for subsequences. So you might be familiar with subsequences. They come up a lot in dynamic programming problems. The idea is that basically it's going to be non-ontiguous, but the order matters. So we could pick like let's say that, that, and maybe this one. See how they're not contiguous. So we have like a gap here but we would say that this subsequence is a b c. Before you go down that brute force backtracking dynamic programming path recognize that we are only considering the subsequences that are length three. So you tell me what would a brute force solution look like? Do we really have to get recursive? Can't we just do triple nested loops? Like for example I have one pointer which will start here. I'll have another pointer which will start after that and then another pointer that will start after that because having triple nested loops we can still guarantee that the relative order will be the same. So maybe if my J was over here now and then my K starts after that this is still like preserving the order. So yes, we can get every single subsequence in three loops. That's going to be n cubed time. And determining if the like if that's a palrum, that subsequence of length three, that's technically constant time. It's of length three. That is a small length. It's fixed. So it's going to be very easy for us to determine that. In fact, if you give me three characters that look like this, I don't really care what goes in the middle. It does not matter. I only care that the left and right characters are equal. So that is going to be very trivial to check. Now the question becomes, how can we do better than an N cubed solution? Does knowing that the middle character doesn't matter help us at all? Well, it kind of does because consider this. If I was like scanning through here, let's say I call my pointer mid and it tells me what the middle character is. Let's say it's over here some arbitrary position. How do I know how many palendromes I can form with this guy as the middle character? Well, here's what I would do. I'll just go through every character on the left side. Let's say I see an A. Well, now I want to know, do I have any A's on the right side? And it turns out we do. So, we have one here. So, we found a palendrome. So what I'm trying to do at this point is say for every middle character, can I somehow in linear time go through everything on the left and everything on the right and just count the palms with this guy as a middle character because then I can get the solution down from n cubed to n squ and yes that is actually possible. One way to do it would be let's say just throw all of these into some data structure uh like a hash set and then do the same thing over here. throw them into a hash and then what I could do is go through every character on the left side and so we have an a here and then I'd say okay let's do a quick lookup a constant time lookup to see if we also have that same character in the right side and that would allow me to count the palendrome so that's the n squared way the n squ comes from the fact that we're having to take all of these and then take all of these and then throw them into a hash set and we have to do that every single time with this pointer like every time we shift the pointer now if I were to move my middle pointer over here. I have to redo that. Now I have to throw all of these into the left side and then all of these into the right side. Do you kind of see how we are doing some repeated work there? Why do we have to do all of these and all of these every single time that we take our middle pointer and shift it? We don't. We could just focus on the new character that we added. Throw it on the left side. And since we shifted the middle pointer, we take this guy and then remove it from the right side. So that's the intuition behind this solution. That's the intuition of how to get this down to a linear time solution. Now, let me dry run through this and show you a couple minor things that I'm going to change. One of them being that I actually don't want a hash set on the right side. I actually want a hash map because if I'm removing a character from the right side, let's say I want to remove the C. Well, if I have multiple occurrences of the C, I want to be able to somehow track that. On the left side, it doesn't matter. We can use a hashet because we're never removing characters from the left side. We're only adding characters. If I have multiple A's on the left side, it doesn't actually matter. And the main reason for that is in this problem, they actually only want us to track the unique palendrome. So if I were to have like a b a and maybe I can form that another way with a second a on the left side. It doesn't matter. It's technically still the same palendrome. So we don't want to double count it. And the easiest way to do that is to keep track of all the palenromes that we've seen in a data structure. I'm going to use a hash set. It's pretty easy to do that. And in fact we don't actually need to store the entire palrrome itself. Suppose we had aba as the palrrome. This entire information can be encapsulated in two characters. We only need the left character and the middle character. You could call this the middle character and you could call this the left or you could call it the outer character. The reason I say outer character is because since it's a palendrome, we know this character is going to be the same as the one on the right side. Anyway, so in fact, we can just store two characters um in our hashet for each palendrome. Now, quickly, let me go through the dry run. So, this is how it's going to work right now. Now this is our middle pointer. I'm going to have my left side that's going to be a hash set and my right side is going to be a hashmap. Initially my map is going to be I have three occurrences of A. I have one occurrence of B and I have one occurrence of C. We basically initialize this with all of the characters. When my middle pointer reaches here, I want to now take this out of the right side because now this is our right side. So I can decrement the count of a by one. It's going to be two now. But so far there's nothing on our left side yet. So now I'm going to take my middle pointer, move it here. I'm going to take this guy and throw it in the left side. So I have an A on the left side. And now that we've removed this from the right side, we can decrement the count of a by one. It'll be one. I know this is a little bit hard to read. So now to count the palenromes where this is the middle character, we go through every character on our left side and check does this character also exist in the map on the right side. And in fact it does. We have an A here and an A here. So we counted one palrome. Middle pointer is going to be here. Now we have two A's on the left side. Doesn't matter. We don't keep track of them. We remove the B from the right side. So the count of B now is going to be zero. Once again, we go through all the characters on the left. It's an A. Look up. Does A exist on the right side? Yep. So, we can in fact form a palendrome. That's two. And now shift middle over here. B is thrown into the left side. B is rem or C is removed from the right side. So, I realized I had the count wrong here. It should have been a one. Sorry. Um, but now we have zero C's. And once again, I go through everything on the left set. A does it also exist in the map? Yes, it does. So once again, we can form a palendrome here. But we check B. B exists over here, but not on the right side, not in this map. Thus, we can't form a palenrome. And finally, when our middle pointer gets over here, I think it's obvious that there's nothing on the right side anyway. This will be down to zero. So of course, we can't form a palenrome. But we counted three total palrums. That is the solution to this. And we're doing it in linear time, but obviously we do have linear space as well. And just in case you're wondering, if we're throwing every single possible palendrome into the hash set, how could that be efficient? Well, think about how many different palendromes we could have given that we're only dealing with lowercase A through Z characters. And given that we have three different spots, you might think there's 26 cubed palendromes, but not really because we know that the left and right are always going to be the same. So we could have 26 different positions here. And then since these are both the same, it's going to be 26 different positions or rather characters for those as well. So it's actually 26 squared different unique palendromes we could have that are of length three given that our character set is lowercase a through z. Okay, now let's code it up. And I realize this explanation has actually gone longer than I expected, mostly because of the dry run. I probably didn't need to do that, but I'm going to start with the result that we were talking about. We don't need three characters in this result. I'm actually going to store a pair for every palendrome that we find the middle character and the outer character. And then to get the number of unique palendromes since we know hashets eliminate duplicates, we can literally just take the length of that hash set and return that to get the count. Remember that we're going to have two data structures. A left data structure which I'm going to make a set and a right data structure which I'm going to make a hashmap. But I'm not just going to use a regular hashmap. I'm going to use a counter because Python makes our life so easy. If you don't know how counters work, I explain it pretty well, I think, in this lesson in my Python for goodies course. And it has a bunch of interactive lessons. So, you can actually like write code and test yourself as you kind of go through this course and learn a bunch of other stuff as well. But basically, this is creating a hashmap, counting the occurrences of every character, just like we would want to do. And it's pretty easy to write a loop to do that, but might as well use the built-in uh way to do it. So now I'm going to go through every position in uh the input string and I probably don't even need to do it this way. Let me actually say for character in string s. This is our middle character. So I'll actually call it that mid. And so now what we want to do is first of all say now this character no longer is on the right side because now it's the middle. So we have to remove it from the right side. So that's easy to do. Just take right of this middle character, decrement the count by one. And you might say, we'll take this character and add it to the left side. Left set dot add this middle character. It's true. We want to do that at some point. But before we do that, we want to now check for all the characters that are currently on the left side. Of course, on the first iteration, that'll be empty, but still we want to go through every character on the left side, and we want to check is this character also on the right side. So if right of this character and the count of that is greater than zero then we have found a palrum result.add this pair the middle and the outer character. It's possible that this is a duplicate that's why we have this hash set in the first place. So now I am pretty much done with that. I think this is the entire code. So after we're done checking that then we can take the middle character and add it to the left side. So let's run it. And here you can see it works and it's pretty efficient. If you found this helpful, check out neatcode.io for a lot more.