Count Vowel Strings in Ranges - Leetcode 2559 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today I'll solve the problem count Val strings in ranges so I'll briefly go over the description but I think it's easier just to really focus on the example the idea here is we're given an array of strings like these that's the first input that we're given and the second input that we're given is a bunch of queries each query so let's say a z two basically means that for the strings that we have here this query is asking for this subarray this like sub array of strings how many of these strings satisfy a specific condition thankfully that condition is actually very very simple in this case basically they want to know for let's say example this word ABA does this word start and end with a vowel when I say that I see a end end I know I'm saying the exact same thing but it's two different words don't blame me for that thank the English language so the last character has to be a vowel and the first character has to be a vowel as well so the first word does satisfy that the second word is over here BCB and the third word is ECE reminds me of electrical and computer engineering but anyways okay so this word here does not start with a vowel and it does not end in a vowel either so don't include this word but this word does begin end and with a V so we have two words in this range and thus the answer to this query is going to be two and basically all we want to do is just answer all of the queries so let me now blow up the example so you can see that in this example the answer to that query was two and so for each of these queries we want to know the answer and then we would just want to populate an array of values for it so for this query 1 through 4 that's going to be I believe this and you can see this one does not satisfy that this one does this one does and this one technically does as well it's only a single character but it is a vowel by the way the vowel set they also give to us this is a vowel a I or a e i o u so there's five vowels it's pretty easy to check if a word begins and ends with a vowel we can just check the first character and the last character and then just do a quick lookup you could throw these into a hash set or you could just have an array I mean scanning through an array of length five isn't going to be super inefficient so it really doesn't matter in my humble opinion but it's up to you this kind of solution is going to be o of n for every query we might have to go through the entire input to check if a word is a vowel I mean we can do that in constant time but how many queries are we going to have let's say there's M queries thus the overall time complexity is going to be n time M can we do better obviously there's repeated work I mean I probably don't have to tell you that but I'll tell you it anyway this query asks check how many of these are vowels and this query asks check how many of these are vowels so among these two sub problems there's already some repeated work would it be possible for us just to check if every single word was a vowel only a single time is there some kind of solution to that perhaps and then lastly we got this query 11 one so I think that's this one basically this problem is about range queries there's several problems that fall into this category of like prefix SLS suffix problems let me kind of show you one that's very very trivial and honestly that problem pretty much just gives you all the intuition for this problem as well if you go to NE code IO which I've already mentioned a million times if you'd like search for the range and the neat code all list there's a few problems I think this one if you're like a very much a beginner this easy one will be a good one and this next one is pretty similar to the previous one they both kind of fall into that prefix category and so pretty good video explanation code explanation in most languages so the idea is going to be like I said prefix suffix queries for us to be able to answer a specific query we don't necessarily know that that query is going to go all the way up until the end of the array if it's going to be from the beginning it could be somewhere like in the middle how do we do it well this is how we're going to create an array that's roughly the same size as this except it's going to have one additional uh spot at the end and so for each of these we're going to determine is it valid or not like is this a word that we're going to count so we can see that this begins and ends with a vowel so we'll do a one over here this one does not so you might think well we'll put a zero here then we'll put a one here we'll put a one here and then a one here and then a zero here but this doesn't really tell us a lot what we want to do is be able to answer a query like this one in constant time how could you do it well if you were just going to have like the prefix uh counts suppose something like this or or rather let's say this value tells us how many of these were prefixes that'd be nice but it's actually not enough if the query we want to answer doesn't actually begin at the beginning but if we also had this prefix count stored here well then we could answer this query by taking this value and subtracting it from that value and that's exactly what we're going to do there's just one tiny little thing and you might be wondering why did I add a second spot or rather one extra spot it's mainly because what if we did have a query that starts from the beginning well then we would take this value subtract it not from this value but the value over here but there is no value over there so I guess maybe a better way to have drawn this would be like this where I'll just slide this over to the right by one so now we can just put a zero here we can check this is a vowel like begins and ends like that so we'll put a one here and now for this one it's not a vowel but we're not going to put zero here we're going to take the previous value and add to it zero since this is not beginning and ending with a vowel so we'll have one here this is so 1 + 1 is 2 this also is 2 + 1 is 3 this also is 3 + 1 is 4 now for us to build the output array answering each query let me just draw a little array of size three for this query which actually does begin from the beginning it's this so what we would do is take this value which is two that tells us how many of these words are valid and subtract from it the value over here which there's no words to subtract so we'll get a two to answer that query for this query it's going to go from one all the way to the end so this value and then from here we'll subtract from it that value because we don't want to include this 4 - 1 is 3 so I'll put a three here last one this query over here or sorry I think it's this one and so that's one subtract from it the value to the left because we don't want to include here so 1 minus one that's going to be zero so you can see it works pretty efficient linear time linear space solution okay so the first thing I'm going to do is just kind of get the vowels that we're dealing with so I'll call it a vowel set and well actually yeah let's uh do that vowel set and then I'll pass in a string a e i o u this will just give me a string taking each of these or rather a set taking each of these and adding it to the hash set then I want to create my prefix array I'll call it prefix count it'll be an array of all zeros and the length will be the length of the words + one and then we want to populate it going through each word in the input of words so in Python I like to do this IW in enumerate if you don't know these little python tricks you might be interested in my python for coding interview scores or maybe you're not um either way what we want to know for this particular word is it a vowel or not and if it was a vowel this is what we would do we'd say prefix count at I +1 remember we're kind of doing that offset cuz we want to look to the right of the current word and we would set it to be the previous one at prefix account at index I and add to it either one or add to it zero depending on if the current word is like beginning and ending with a vowel so let's just get that let's call that V is it a vowel or not I'll set that to zero initially and then I'll say this if the first character of the word is in the vowel set and the last character in the word which conveniently in Python you can get with1 one is in the vowel set then we can increment this by one we could have also done this with like a Turner operator I just think it would have been kind of unreadable since this is like two conditions but it's up to you and then here we can then add to this V because it's either going to be zero or one and that's good this code actually can be made a little bit more concise rather than just taking the previous value we could just store it temporarily like in a variable let's just call it previous let's initially set it to zero and then we don't even need this anymore and then if this condition is true what we can do is take previous and increment that by one whoops and then for the prefix like since this is now the correct value we can just set that here set that to previous and then we're good this is already updated for the next iteration this optimization doesn't really matter I just know if I didn't mention it there's going to be at least one person in the comments saying you can make it shorter which is fine if you guys do think of like better ways to write it up you can always copy and paste your code into the comments maybe people will find that helpful okay now to actually answer the queries we're going to have an array of results it's all zeros it's going to be the length of the input queries array and then we're going to return it before we do that we should populate it so for each query I'm going to do this for IQ in aerate the queries we're going to unpack the query the left and right boundaries of it and now the result at index I will simply be the prefix count from WR + one remember that plus one comes from the fact that we do have an offset subtracted by prefix of left because if left was Zero we would want the prefix to always be zero that's why we start at I + 1 that first zero will always be there that's pretty much the whole code let me just run it to make sure I don't have any bugs of course I do and of course it's always a typo maybe I should have just called that array prefix I forgot the underscore count but now you can see that it does work and it's very efficient if you found this helpful I think you'll also enjoy some of the content on NE code. I made some updates to like the Big O notation crash course here and all of these things like this part is completely free if you check it out on a NE cod. I think you'll find it useful thanks for watching I'll see you pretty soon