Find Common Characters - Leetcode 1002 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem find common characters we're given a string or basically a list of words and so the way this is worded is honestly kind of confusing to me but let's break it down we're going to return an array of all characters that show up in all strings within this list I feel like they probably could have used the word every but you know that's just me so what does that mean and what does it mean when they say include duplicates well the idea is basically just look at the example don't even bother with the description half the time these are the words we're given Bella label and roller which characters are common to all three strings it looks to me every single one of those words has an e in it and every word has an L in it but the result is not e l it's e l l and that's because every word actually has two L's in it this has two L's this this has two L's and this one has two L's so this is the result B is not common to all three it's common to the first two but not this one R is not common to all three either a is not common to all three etc etc so that's the idea now how do we solve this problem obviously the fact that there are duplicates in here highly suggests the fact that for every given word let's at least count the occurrences of of every single character so let's do Bella looks like we have a single B looks like we have a single e we have two L's I'm not really sure how to make this look not like a one but um and we have a single a we can do that for the other two words I'll just kind of fast forward that so we counted the words now let's just go through every single character B it looks like it's in these two words but not this one so we can't include that in the result what about e it does look like it's in all three strings and it has a count of one suppose this one for some reason had two e's in it what would we do well we'd say this one has one e this one has one e this one has one e it technically has two but we have to take the minimum right we have to take the intersection of these three and then minimize it so we'd say we can only have one e in this case though this one already has one e anyway so it makes our life easy so we just put an e down here next we look at L it's in all three of these so the count of it again is two we take the minimum and it's two in all of them so we would take two if suppose one of these only had one L then we'd have to take the intersection these have two L's but this one only has a single one so we'd have to put one L but that's not the case each of them has two so we can put two L's in the output last a has a count of one in these two words but it doesn't show up in this word now you might think well don't we also have to look at some of the other characters like we only looked at b e l a we did not look at R nor did we look at o but my claim to you is we actually don't need to look at the keys of every single word because we only care about the keys that show up in every single word anyway so it doesn't matter whether we iterate over the keys in this word or we iterate over the keys in this one or this one we just have to pick a single word and then check which of those keys belong to every single word the answer will be the same like in this word we see that e and l show up in the other words as well R doesn't o doesn't either so now this solution does work this is a perfectly valid solution just count the occurrences for every single word then just pick one word arbitrarily go through the keys of it check does the that key exist in all the other words and then minimize the count this works it's kind of complicated to code up and also if you think about the space complexity every single word will like an individual word will only have up to 26 distinct characters lowercase A through Z I think but the number of hash Maps we're going to create each one of um is going to be constant size that's what I'm getting at with this but the number of hash Maps we're going to have to create is going to be proportional to the number of words in the input let's say that's n so the overall space complexity is going to be Big O of n we can actually reduce the space complexity to one and I'm going to show you how that is we're going to take let's say one of the words this one and then we're going to build a hashmap with it so this is constant space so far once we have that hashmap we're going to say okay this is the most amount of characters that could possibly be in the output like we can never have more than a single e in the output because if this word doesn't have multiple e it doesn't matter how many Es the other words have because we have to minimize the count so okay so this is at most the number that we could have in the result now we're going to count a second word let's pick this one just to make it more interesting so we have these two hashmaps in memory this is still constant space having two hashmaps that are of constant size is still constant now what we're going to say is find the intersection of just these two before we were finding the intersection of all the hashmaps at once but now we're going to do it pairwise we're just going to look at two hashmaps at a time and so I'm going to pick this one to iterate over let's check B is that common to both of them no so what I'm going to say is screw this B is never going to be in the output cuz we found at least one word that does not have B okay let's try e okay it does show up in both and the count is the same so let's keep this what about L shows up in both count is the same what about a it does not show up in this one so screw it we only have these two left this is the max that our result could possibly have so we've gone through this word and we've gone through this word now let's look at this word throw it into a hashmap and then start comparing let's check does e show up in both yep and the counts are the same does l show up in both yep the counts are the same so now we've gone through every single word this is no longer in memory this is the result but the only thing we have to do is take this hashmap and convert it into a list of characters I think you probably know how to do that we're going to iterate over every single key so we're going to have a loop for that let's say every single key in the hashmap and then in this Loop itself we're going to iterate for however many times let's say I in the range of this quantity this number so in this case it's one so we're going to add a single e to the output and then we're going to iterate two times for L and we're going to add two L's in the output and that's the result so space complexity as you could tell was constant what about the time complexity well in the worst case we're pretty much iterating over every single word in the input we're doing that to throw them into half maps and then we're potentially going through the unique Keys that's not going to be super expensive though this is the bottleneck so overall time complexity is going to be let's say n is the number of words let's say m is the size of the longest word or the average length of the word it doesn't really matter and this is going to be the overall time complexity in that case the beautiful thing about python is that we can actually take a given word and get the count of every single character very easily we can call counter let's say on the first word we're guaranteed that there's going to be at least one word in this list so we don't have to worry about index out of bounds so this will return a hashmap with the count of every single word great now we want to go through the rest of the words what I could do is say I in range from one to the length of words but actually this solution is going to work out the exact same even if we were to iterate over that first word once again because when we take the intersection of the first word with itself it's not going to change this hashmap at all that's why it works and I prefer this cuz it's more concise but it really doesn't matter you can do it the other way if you want to save one iteration now I'm going to take the current word I'm going to call this current count I'm just going to call counter on that word as well so now we have another hashmap with a count of every character in that word next I'm going to go through every character I could actually pick either one I could pick uh this one or this one I'm going to choose this one just because this one is never going out of memory like this one is declared out there and this one we're going to keep reassigning anyway so I'm going to say for character in count and I'm going to say let's get the count of this character in this word and let's get the count of this character in the other word and I'm going to take those counts and try to minimize them and then I'm going to reassign that back to this one it's possible that maybe this character actually doesn't even exist in the other hashmap in that case counter is kind of like a default dict this will evaluate to zero so in that case this would end up being set to zero basically telling us that we don't want any occurrences of this character in the output so this is pretty much just to get the count of every character that we want in the output that's what this portion of the code is doing now is the time to actually build the result build that array that we're going to end up returning so I'm going to go through every key now that's in this hashmap and I want specifically the count of this character so I want to Loop that many times it could be zero so we might end up looping zero times so I'm going to say for I in range whatever this count is it could be zero or it could be a positive number if it's a positive number we want to add obviously this character this many times we will just do a very simple operation append to the list that particular character however many times we want to could be zero or it could be more than that and then return the result it doesn't matter what order we add the characters in so that's the good part if it did then maybe we could sort it or something but now let's run it and as you can see on the left this works obviously the space is efficient the run time is pretty random I don't really worry about this this is about as efficient as we can get the solution obviously we have to go through all the words if you found this helpful check out N.O for a lot more thanks for watching and I'll see you soon