Strong Password Checker (HARD) - Solve with Sam in Python

hello good morning Sam here and I'll be doing another lead code question today instead of a random one we're doing a lead code hard number 420 strong password Checker which was recommended to me by a viewer timla 6487 I think so thank you very much tin for forwarding this to me this looks like a really fun interesting question and we're going to try to solve it blind I will admit I saw the question beforehand once they linked it to me so I have a little bit of an idea of what's going on but we'll still try to solve it together so I hope you'll enjoy uh watching it with me I'll have the link below so let me know if you tried this problem yourself what kind of hung you up and what didn't I have a feeling this is going to take me quite a while if I do get it at all so maybe for the benefit of everyone I'm going to cut the video up to remove a lot of dead spaces the timer over here in the top right will still be accurate it'll just be you know clipped here and there so without further Ado let's have a look at the question let's get myself small again no need to see me that closely okay so 420 strong password Checker a password is considered strong if the below conditions are all met it has at least six characters and at most 20 characters okay you know what I'd like to do is actually I'm going to create a little G do here where I'm going to keep my notes I tried doing it with the markdown inside of Le code itself but it just doesn't work for me so we'll just kind of jump back and forth to this so we want a good strong password has 6 to 20 characters so that's number one and let's see what else is there it contains at least one lowercase one uppercase and one digit so a a and digit something like three unique characters needed at least one of them it doesn't care how many there are it does not contain three repeating characters in a row okay that's interesting so we don't want a a a i e a a a or something like that or 111 that's the only one that's giving me a little pause right now cuz here's what I'm thinking right now the first two are pretty straightforward we can check if a password is strong or not just by counting through them and so on this one is pretty straightforward to do in like a leak code easy to check if this three repeating characters but now here comes the Crux it looks like given a string password return the minimum number of steps required to make password strong so we're trying to find the distance character distance between the current string password it looks like and a valid strong password the ways to do that is three steps so we're trying to convert given string into strong password if already one then zero steps needed that's kind of interesting insert one character to password you can delete one character from password you can replace one character of password with another character so this kind of makes me think of something called 11in I might be spelling this wrong 11in all right that makes more sense so for example the difference between this these two is about two characters changed so two that's an example for this too and I I do know that for 11 lein you can kind of solve this with dynamic programming for n * m I think for n cares and M cares between two words and it might be even better than that but that's something that's just kind of coming to mind right now I'm not sure if that's relevant just yet because one of the things I'm realizing is we're not given some other password that's strong to compare to so we actually have to find that ourself actually we do not have to find that our we're just thinking about the distance to it so we don't actually care which letters we remove we don't need to actually modify the input string we just need to count how much effort is required to change the pass so actually I think that makes the problem quite a bit easier thankfully cuz I wasn't sure let me just talk through what I was thinking at first so approach one if we needed to know exactly what the strong password was then what we need to do is some some sort of dynamic programming or bread for search where you try different steps and keep growing and you could even do some sort of AAR thing where with heris stick if you wanted to to score how close to a strong password we are these are opt we could have done this would have become some sort of I mean NM or greater which is not bad but I'm not sure that's what we want to and it it sounds really hard to me just thinking about it right now so I'm glad we don't need to do that because we don't need to know the strong password just the distance to it so this is a key point because we can do a here's a couple things I'm thinking about let's just start with the simplest one how would we calculate this distance if we only had the first requirement of 6 to 20 characters this would be an o of one if only a length mattered then we could calculate the distance is equal to the difference between let's see it's like the max of zero and the length of the characters six minus the length of the characters so if n is smaller than six let's see small disc you know it would be something along these lines or Max of zero and 20 characters or more if it's more than 20 characters it would be like that if greater and if less and we could turn this into a oneliner this would be a o of one type solution we don't even need to know what characters they are that' be super easy now if we also include three unique characters so let's just add this one now then we just need to do a oent iteration count each unique care if they exist and if they don't this is where it kind of gets interesting with the first one when you're adding characters you can add those new unique characters if you're removing characters do you need to worry about removing those unique characters do we need to worry when remov moving characters part of me was wondering like so let's just say we had some string abc1 2 3 ABC you know that has all of our unique things and no repeats equal to length 9 and let's just say we need it to be length eight here it doesn't actually matter but let's say if it was lowercase again and there was just the one upper case C we don't need to worry about removing the wrong one cuz we can always remove some other character we know that there are six to 20 characters so we can always there will always be repeats of those three unique characters inside there and we can just choose to remove another one can always remove a unimportant care so we don't need to worry about removes messing things up I think that'll be true even once we start to have repeating characters cuz let's say with their given example here you don't want to remove let's change that up and make it like this so in this case don't want to remove middle B because that causes a sequence if we had to know what the strong password was this would start to matter when we do our bre first search dynamic programming solution but since we're just thinking about distance we don't need to worry about that and we know there's always going to exist some character we could remove instead like say a instead of this one we don't want to remove B can always so we can always remove an unimportant character and I think that's a really important distinction that makes this problem a lot simpler sorry if this is kind of going all over the place I'm just thinking about different things before we dive into the code I want to kind of talk it out with the interviewer as I do it cuz if we started coding and I started coding up a dfp or BFS approach I could have used up the whole hour as is already though we are about 1015 10 11 minutes in so we don't want to waste too much time time okay so we can always remove an unimportant character when we add characters we can always make sure to add characters that are can always add characters that don't mess up the other requirements we can always add different letters we don't care what they are but we know that if we needed to add another two letters it doesn't have to be CC we could just choose it to be you know any any arbitrary character so this makes me think about the concept of introducing introducing wild cards when adding removing this isn't relevant just yet but this do apply to other problems like Word ladder or anything with anagrams where you can kind of hash anagrams with wild cards to find the connections between two words if they're anagrams of each other I think I have a question like that somewhere in my YouTube channel if I do I'll link it above otherwise next time I see one you should be able to find it okay what else have we got now the the one I've been kind of avoiding so the the key one here is it does not repeat contain three repeating characters in a row let's think about that one H so what what could we do here we can remove characters and that's fine but let's say just say we had a a a a you know or three letters of a how many characters do we need to remove to get rid of the sequence you need to remove two to make valid SE no sequence of three what else can we do this is where we this is how we create instead of adding and removing characters we can also replace characters and I think that matters here because we don't have to remove two anymore we can just change one so let's just say we change the A and two so arbitrary character like B edit one to make valid okay that's cool sorry the frustration I'm having in my head now is thinking about how to decide between whether to edit or remove something I think we always want to edit edit faster then remove cuz even in the best case scenario where we have a AA remove one to make valid or in the worst case AA remove three to make valid actually you know what's interesting here a AA a a a remove forward to make valid but what happens for edits let's put this in order starting to see a pattern kind of form actually so we always have to remove we remove n minus 2 to make valid so that's the pattern I'm seeing there but for edits edit one a XA and for this one edit one a a x a a for this one edit oh wait sorry uh this one is a AXA like that a AXA a so that's also an edit one that's cool now we have to do edit two a a x a ax a something like that edit this one and this one actually arbitrarily and then for N I don't know exactly what the pattern is yet but it seems to be some sort of relationship to threes I think there's going to be a mod three involved or truncate divide by three and the reason I think that is because we're always trying to break up sequences of three so three is going to be involved somehow whether it's 3 - one or plus one it's going to use that in the math somewhere not sure about the pattern yet but I think I'm seeing something here so let's just see let's just say we have this concept I I haven't fleshed it ey yet but let's think about it the idea is inner code will have a sequence the idea is sequentially count and do a couple things we'll count the length get a count of cars needed to be added get a count of and is this big enough actually let's make this a little bigger just to be easier to read so I want to get the count of characters to be added and characters to be removed moved get all sequences of characters then I'll do some sort of get count of edits needed but first first count how many first if any car is to be removed or if we need to add characters we can add characters inside to break up the sequence first if any characters are to be added or removed modify sequences sequence lens based on the number of them then after we do that we get kind of Ed his it to break sequences and then we're just going to return the total is going to be some sort of combination of car's add did removed and edited and return that so that's going to be the general logic of what I'd like to do in this code so let's let's start trying to write some of this up so how should we do that we're about 18 minutes in yeah I think it's a good time to start so here we are hopefully you don't have to watch me do this too much there we go let's get a count of the characters that need to be added add call a need add is equal to the max of zero and oh let's first get n equals length of password and if n is equal to zero we don't do anything I'm just adding this special case cuz I can already tell I'm going to have issues if the password is empty we just return six cuz we need to add six characters to make it a valid password all right if the max if the length of the password is smaller than 6 so if it's 5 then 6 - 5 is 1 we need to add at least one then we need to count characters removed is equal to the max of six we need at least 20 characters so if n is smaller than 20 20 - n if n is bigger than 20 then this will be a negative number Max will be zero I need it the other way around I think n minus 20 if n is bigger than 20 is 26 let's say or 25 25 - 20 is 5 that's correct if it's smaller than 20 like 15 characters it'll be a negative number so max will get us to zero so we get that only one of these will ever be true or both of them will be empty both of them will be zero otherwise maybe we could do something smart with that at some point how do we get the sequences of all characters okay let's do something called sequences it's going to be a list I think I'd like it to be something like character and car count in sequence and there'll be a bunch of them so let me just show an example as I'm doing this uh so let's say we had our example of something more interesting what's do we have any good test cases here no let's create one how about uh a a BBB one one one one sure so in this one I would expect to get something along the lines of a 2 cuz there's two of them B and three and C sorry one and four you know something like that to do get sequences then let's say we have our sequences we want to do something with it then adding a character between letters I think I noticed something so one thing I'm noticing is if we have our sequence here if we had it if we had to add a character it's going to do the same thing as editing except just making the sequence longer so the count or adding versus editing is equal I'm not noticing adding and editing is equal no need to do special check for ADD and what I mean by that is we're eventually going to get a count of the edits needed to break the sequence anyway so or ads we'll just take whichever one is larger so let's say we count to do something and then the total will be the total equals the max of need add need remove and can you do multiple Max Max of multiple things at once I don't remember and need edit and need edit will just be for oh we also need to count unique characters so where is the unique that one actually I think we can do straight away get count of unique characters needed need unique so in the worst case it'll be three because you need all three unique characters then we need to check if we have has has lower minus has upper you know just create I'm going to create these has a number I think that already exists in Python somehow so let's just see hasor equals password any c do has lower I think that's how it is for C and password and I think we could even do well I don't actually know so let's change this to has upper and finally unique has number and I'm not sure what that's called I think there's something like has digit or is digit maybe it's is is upper is lower for any character so then these are just Boolean values and you can subtract Boolean as a one if you have all three of them it'll be zero otherwise it'll be up to three so we'll take the max of well actually is that separate when you add or remove charact when you add characters you can also do the edits but subtracting characters need remove I think is how it works you always need to remove characters and we're subtracting the edits you're always going to need to edit or add new characters and unique so these will be added together instead of so combined as the Mac so I think this will be something like the total return the total okay unique characters there Max of the ads and subtractions are there so let's get that those two can stay nice and clean that's going to stay true regardless of the sequences let's figure out the sequences now so let's say we've gotten our sequences now we need to just check for removed characters so the way I'd like to do this is let's say we here in this sequence what I'd like to do is for each car removed remove one from best sequence so we have our sequence here while each care something like that we'll start with the original and what I'd like to do then is remove in this case either ooh okay this just got this is has to do with what we were looking at uh in our G do so I noticed in the G do that removing isn't always better than editing okay let's just start simple and let's say we removed always the the largest one the one the longest sequence so this goes down one this goes down two then this goes down three you know let's just pretend it was something like that then we iterate over the sequences then we need to count the edits and the way we can count the edits I think will be relatively easy what I'd like to do is just count well no that's not true the number of edits is related to this ratio I think it's actually just the length of the string divided by three truncated that's my guess is that true here what's the length 3 6 and 6 6 / 3 = 2 that's correct 5 length 5 5 / 3 = 1 yeah and there one for these two yeah that's correct and let's check it for something really long 1 2 3 4 5 6 7 8 9 10 11 12 13 14 let's just say it's 14 14 length how many do I need to edit 1 2 3 4 so 14 / 3 should be equal to 4 3 * 4 is 12 uh 3 * 5 is 15 so yes cool so we have our logic actually the number of edits for each sequence is the length of the sequence so will be the count ID three for care count in sequences and it'll be the sum of all of them and technically you only need to do it for sequences greater than the length of three but when you have a sequence of three or less the division when it's less than three you do want it for three it'll be one but if it's less than three it'll be zero and then Su of that will just be zero so this should be correct I'll probably be making a lot of mistakes as we're going through this right now so if you're noticing them as I do it sorry about that please let me know in the comments it's kind of fun to try to solve this together and I think trying to go through these examples live is one of the ways I'm trying to find it I'm really trying to avoid running the test cases until I have a pretty strong confidence in the thing working though I have a feeling that's not going to happen in this case let's find out 30 minutes in so far I think we're getting close we have this kind of logic for the need edit I think counting the sequences I'm not too worried about let's actually go ahead and start doing that the reason I was holding off on doing this is cuz I wanted to make sure this would actually work before we do it and I'm noticing one thing is that idea of the best sequence this is not the most optimal way to fix this problem because we are count when you count the number of edits for this problem you have one needed in the B and uh that's it so you have one so you let's say we removed uh removed to need one edit still so this is actually pretty bad whereas ideally what we'd like to do remove this one and then we only have to do one edit at that point and edit still so that's uh two instead of three so what's an example that this would matter let's say we had a a a and bbbb there we go so the simplest thing you could do is two edits a XA and bbxb uh and actually we're ignoring unique count characters and things like that you we could add them into the end let's just let's you know A1 at the end there sure and the length of this is valid so we need two edits to make this valid let's say we need two removes so if we removed this a and and this B actually the second one doesn't matter then we only need two removes and one edit if we had to have two removes in the naive case if we remove just these two let's let's just say two of the be cuz they're the longest we still need two edit still need two removes plus two edits needed to make this valid but instead of doing that if we had remov one a and one B then this could be fixed with a single uh edit of uh this letter B for example you know so the length of the string is not enough so I think we need to choose the best somehow scoring the sequences I think the best sequence is going to be related to the mod 3 because it's AAA is the best one to remove because it's mod three of the length three is zero so once we remove one we've removed a whole edit required whereas Mod Five is two so even if we remove one we're still going to need an edit until we get down to let's say we have six this will require two edits because 6 / 3 truncated is two and 6 mod 3 is zero when we remove one now that goes down to one edit so actually that I think that works really well best sequence is lowest mod 3 so let's create a function called uh score sequence or something like that and we'll have a sequence and I think it's time to make the sequences actually and we'll get back to that so how do we make the sequences we'll create some sort of loop we'll start with i equal Z we've already checked that the string is not empty earlier so that makes this a little easier uh while I is less than n we'll start with car is equal to password of I and start I is equal to I and then while I is less than n and password of I is equal to C uh + one so that'll just keep incrementing it until it gets to the end of that sequence and then let's create our we already have created our sequences and now we just do sequences. append the Tuple character and its length which is equal to I minus start I cuz do we do plus one no because we plus one until it fails or we reach the end of the string and then we just take that so it's already plused one in there so that'll get us our sequences I think that's all you needed and the sequences ordering iset just related to the original password at the moment so how do we score a sequence and let's just say we have some function that can do that so what I'd like to do is for I in range need remove I think is what I called it earlier so if we don't remove any characters we're not going to do anything here and now this is the part where I think is kind of interesting I want to sort the sequences based on sort gives you a lower score is better so I want to sort it in order so lowest first and we're going to use our special key of score sequence and then we take the first one and do something with it so sequence is equal to that and this is not optimal yet this is o n log n or k log K let's call it and this is going to be worst case o of n for n cares assuming like the password was super long so this is going to become some sort of O NK log K which could be I don't know this could be made better it's some sort of Heap sword Heap Q Heap push pop Etc could make this better I'm not going to do that just yet cuz that seems kind of complicated maybe we'll come back to that so let's just keep that as a to-do so we have our sequences I want to modify this sequence we have to remove a character so we're removing that sequence's character new sequence is equal to sequence I I wanted to remove modify it in place but I realized it's a tupal so I think we have to create a new one so sequence Z sequence one minus one 0 equals new sequence I think that's just all you need to do we don't even need that so assuming we had a proper scoring process it would find that sequence let's say it's this one it'll subtract the second value and bring it down one as we want and it'll keep doing that until we've done removed as many characters as we want I was wondering if we need to set does after this does need remove become zero no cuz that's still an action we're doing so we don't do that but it will remove the number of edits needed later on so that's good Okay so we've reduced our sequence based on remove and we just count the sequences and car I think we might be getting close to the end what time are we at 40 minutes this is a this is a long one guys oh we need to score the sequence so let's just start with lower is better so so let's just say the car and count is equal to sequence count is greater than six or sorry if count is less than three we return some arbitrarily large number so I need to let's get rid of the G do so what I'm thinking about here is how to make this score sequences if no changes needed we just return the some max value since we know the length of a password can no be no bigger than 50 we know this thousand will be bigger than that this could be changed to some sort of maxent or something like that the input password is always considered consists of letters edges and dots or exclamation point I didn't go over this in the beginning because I just kind of assumed it from the leak code sorry about that we did talk a little bit about other approaches but this one kind of seems to be the general main way to go about it I think it's important to split up the code into different pieces especially when you're doing a leak code hard question I I don't want to have to focus on everything at the same time otherwise it gets too overwhelming so you saw how I kind of broke it up into different chunks now I'm just focusing on scoring sequence if the count is less than three we don't need really need to remove this one unless there's no other better option so it'll be high score otherwise now we want to check mod 3 so count mod 3 lower is better mod score is equal to that lower better as is we also then just return that directly I think so return mod score and this will will then reduce those that are three but then I have a question now is which one is better to remove if you had a string with let's say three here and then six here and so technically this will be you know like three is three of them let's actually do A and B sorry that's a little easier to read so a has three and B has six this is all this would be ideally what the sequence looks like would it be better to remove right now the score for both of these would be the same is that that's fine cuz let's see if we wanted to edit this we would have to change one here two here actually so there is something interesting there I think if we remove from here we still need to do two edits but if we remove from B we still need to do two edits but we only need to do two edits like that I think it's better to remove from the larger sequence if the mods are the same that's my intuition intuition reduce longer sequence the way we can do that there there's a reason I'm making this a separate function cuz I don't want to try to write all this logic inside of a key Lambda right here so assuming the mods are the same I want to also have a length score and that's just the length of the actually that's just count longer is better so we need to negate it so negate and then we can return a tuple of this as the length grow and the mods gr so if the mods are the same it'll then compare by the second one that's kind of how the key sword works so I think that'll then choose the larger of the two okay now let's remove all this I think we can come back to it if we need to yeah the best SE is not just the long I think longest lens still is useful but it's not as important as the mod sequence primary and then L score better okay I think this does everything we need now the logic just needs to apply here so I'd like to check it for this password A1 so with A1 let's just say we have our n equal 3 so max of 6 - 3 is equal to 3 Max of 6 - 20 is a negative number so it's zero we're not doing any sort of removes or sequences does it have an upper does it have a lower yes does it have an upper yes does it have an number yes so 3 - 111 zero this should be equal to zero and the sequences will then be equal to for this one it'll just be one of each a a and and let's just confirm that's how we do it I is zero I is less than three 0 is less than three first character is a lowercase a start index is zero valid is equal to I + 1 is now one still valid no no it's not valid anymore so we moved on WE sub pended a and one then we do the same for a capital A and then we did the same for one and I think at the end I'm just trying to check for any off by one error here think we're okay finally we want to score it doesn't matter here so what happens when then the need edit is counts of the sequences this will all be zero so this will be Zer so now the max of this is equal to uh Max of 3 0 0 + 0 = 3 and that is the correct answer so I think we are good I think we probably need to do some other checks but I I don't want to run make this video run too long so for the sake of let's just have a think a is one it'll be upper and lower upper and number missing so it'll be need unique is two and need add is equal to five Max of five and two and zero is five need to remove none so five and that is five that's correct this one will be all valid so everything will be zero so it will be zero okay let's test it and see what we get nope okay first error is this no is lower what is the python function for is okay it's just without that let's try this again oh good all right accepted 53 and zero trying to think of some other edge cases I'd like to add really quick but how about we add a test case let's create some new ones I want to make sure it works for something like a AA BBB BBB all right let's see how that looks yeah you just remove three and it'll remove the right three okay cool I'm interested to see how this works on the final so let's submit and see what we get fingers crossed I hope this works ah runtime error tupal I should have done a check with the sequences not supported between instances of tupal in and I think I just have a typo type error line 47 less than goodbye score sequence sequences sort oh less than not supported between instances of tupal and int oh right I have to return another tupal here so let's just try that again and let's do a check with this password right here that we we don't have to submit it every time I should have uh kept kept track of that one that's okay all right let's try that and see how that looks good it passes that test case also we're submitting it let's see how it looks right come on yes okay not the most optimal solution but I'm happy to see that we got accepted on our first well not our first submit but without multiple errors at least this one was more of a typo I'm just going to go with uh don't at me too much okay uh I agree this is not the most optimal solution for sure but it is functioning which is always a good sign in a hard problem I wouldn't expect us to be implementing a hard for a mock interview or for a real interview even for uh up to like L5 senior level like it it usually this isn't showing this is showing a little bit more in terms of like organization and breaking up the code into manageable chunks which I think is very valuable um in terms of speed improvements I think we could probably use heapq uh here instead of a sorting uh the array and I think that could get us a bit of a speed up so let's think about that there's probably so many other optimizations as well but I am happy to see that we did it in under an hour we're at about 53 minutes now so I I'm going to call that a win pretty happy about that and uh I'd be interested to see how you all did as well let's think about some optimizations here now so the biggest one in my head is this Heap Q concept rather than scoring the sequences and what I like to do is we've created our sequences here and then i' like to kind of do some sort of um I think we already have heapq uh included Le code provides it so we could do some sort of heq to heapify the sequences and this is O oen I think it becomes oen optimized for Heap Q in place linear yeah and that's kind of nice the problem is that we can't pass in our scoring function to this so and I'm just going to keep kind of talking out loud about what changes would happen here ideally what I'd like to do is do some sort of Heap q. Heap Heap pop and that'll be our sequence and then we modify our new sequence and then Heap q. Heap push this is essentially the what I would like to do and both of these are ol log n or log K in this case we're still doing o of n so with Heap Q we'd get something on the order of o n log K which is a lot better I think that would give us quite a bit of speed up too so let's see if we can make that happen the way to do that is we are a heap Q is a Min Heap so that stays the same but we need to pass we need to modify our sequences to have the scores at the front of it so to do that it will be score sequences is equal to score sequence for sequence quence in sequences and the score is just going to be score sequence of sequence there so then we heapify this and we're going to be playing with that instead so we'll do a score and sequence from the heapq that pop new sequence is that new score is equal to score score sequence the new sequence like that and then we he push our new score and new sequence and I think we can make this a little bit cleaner also by taking the the head of the oh sorry Heap pop scored sequences heapq the push onto it scored sequences I think instead we can do scored sequences zero I don't want to pop it we can do a replace Heap replace that'll be a bit faster CU that basically pops the minimum and replaces it with a new one and it's a bit faster you often use that in heapq operations slight optimization hopefully sequences or score score we actually don't even use that score so we'll just ignore it think that works and then at the end of all this yeah let's get rid of that we need to get our sequences up back to normal so sequence for score sequence and scored sequences so this there's a name for what I'm doing here it's like uh amending the array or something for it's like adding score modifying TOS for apify and then you unroll it all right so that should do the same thing and nothing else changes except now we're using a slightly more optimized algorithm and data structure let's test with our test cases first still passes happy to see that and let's submit and see how it does yeah much faster we're now in the center of this kind of distribution I'd be interested to see what kind of optimizations there are to be made Beyond this I think there are probably several this generation here's one I think would be better is if you could somehow unru this function so you don't kind of generate it on the fly when you're generating the sequences I think that's one way you could do this and then instead of doing it separately that would probably save us a couple milliseconds but this is kind of within the range of the back end so in terms of algorithmic complexity I think we're getting close to the optimal well actually please let me know in the comments if you see any major optimizations or even just any optimizations that you found that I haven't yet this is a fun problem I think there's a lot of spaces for the interviewer to kind of ask more it does require you to feel very confident with doing string manipul string iteration processes like I think you could have done this in a single for loop with some extra variables but this I think will be fast enough cuz you're iterating through the while Isn so it's not a double for Loop and I think it's cleaner this way as well having understanding of generator functions knowing about heapify this main concepts of being able to remove characters to yeah I think this is the key logic and we got that inside of our main edit let me pull that back I could have easily ran out of time so much earlier if I had not thought about the different approaches we had here so I didn't actually talk about too many other approaches I think the only other one that really made sense to me was approaches involving dynamic programming or bre first search that first search something like that I think you could do some sort of like growing out the graph and finding connections things but that only matters when you need to know what the password is going to be here we are able to get to a solution that is faster I think and by faster I didn't actually talk about that let's have a look here so assuming n is the length of the number of characters in a Str everything here starts off as being o of n o of n nnn we're never going to do better than o of n ideal is always going to be at least o of n time and then for space of one ideal don't think we're going to have that in this case cuz we are generating so we're still 111 nnn here this is n this could in the worst case we have to keep track of sequences I think oh K let's call it for K sequences space is being used here and K could be n so we could say o of n space all right it'll be practice a very small percentage of n but still o of n scoring a sequence is mod length this is a o of one operation which is good to see thank goodness o n eify is O of n because of this a linear for a existing array which is super cool and here we have o n log K that becomes our latest biggest thing and this is O of n yeah so at the end of the day we're looking at this solution is O of n log k for n cares K sequences or of K space or end cares K sequences that's what we're at so let's keep that's a good thing to kind of bring up with the interviewer I am trying to think I think you could possibly optimize this by doing all of these in one Loop that might save you a little bit of time but not truly relevant here I think the real trick will be somehow unrolling this into a single for loop with the other stuff as well as maybe pulling in the scoring of the sequences all at once but that is that's for maybe programming optimization I wouldn't worry about too much here trying to think of any other things let's have a look at some of the code that they did oh sorry you weren't able to see a lot of that were you my apologies so let's look at some of the other solutions they had this one right here the fastest one it looks like they did the same thing here they have some initialization of variables they iterate they do checks uh one by one by one this is technically less algorithmically efficient I think because you're looping and then doing three checks for each single one but as we see here that doesn't matter because it's so optimized in practice it'll more than fast enough yeah building up the sequences it doesn't actually even store the sequences I think that's one smart change they have there they're just keeping track of the number of changes use the same trunk a 3 modu 3 for number of changes it looks like there's some small math tricks we can do here that might save us with one change or two change I think that's really cool and finally based on the lens you can do the max of only subsets and only after that do you actually need to do the sequencing stuff and they do some interesting tricks here minmax yeah two change one change there's this concept of one and two changes which I don't yet understand I think it has to do with if uh if the length module of 3 is zero or if it's right off by one then it's plus one or two change okay that's kind of cool these are super cool optimizations when you're trying to compete in competitions and so on but I'd say for a technical interview is not necessary even all the way up into senior level and Beyond getting to this point I think would be very helpful it's okay to not solve the problem completely but being able to explain different steps and how you broke it up being able to write it inside of the Google Doc should be good by the way this was very very fun I really enjoyed uh doing this problem with all of you and thanks again for sharing this problem with me to the viewer this was a really fun one and I hope this was helpful for you and hopefully helpful for anyone watching please send me uh send me a a like and comments uh for any questions you're interested in I'll try to get to them that was actually quite fun so hopefully we'll have another one soon and see you all next time cheers

Channel: Sam Does Leetcode

Views: 229

Keywords:

Id: TMT2DZAvAvM

Length: 39min 55sec (2395 seconds)

Published: Thu May 02 2024