Get Equal Substrings Within Budget - Leetcode 1208 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem get equal substrings within budget we're given two strings of the same length and an integer Max cost consider this example where the Max cost given to us is equal to three so the question we want to know is how large of a substring can we take from s and transform it into the same corresponding substring in a t so for example this substring corresponds to here and if we want to change this one to this one we have to change this a to a b and this B to a c and this C to a d The Catch here though is it's going to take us some cost to change each character and in this problem we're taking the asy value of lowercase a and the aski value of lowercase b taking the difference between them and then getting the absolute value because we don't want to deal with negative integers so in this case it's going to be one this one is going to contribute to our total cost so initially our cost was zero and now our total cost changing it to a b is going to be total cost of one so we just want to stay within this budget and we want to try to create the largest substring that matches in both strings let's try to think about the brute force and then see if we can optimize it at all first of all just to simplify this problem let's do a little bit of precomputation I'm going to take both strings and I'm just going to take the difference between each corresponding pair of values so the difference between a and b is going to be one B and C is going to be one C and D is also going to be 1 D and F is going to be two now just in case you're wondering how am I calculating those differences well just think of it as this a b c uh d e f i don't want to talk too much about like what aski values are so I'm just going to kind of give you the very simple explanation the difference between two characters is pretty much just like the distance between them in this string so A and B the distance is one obviously what's the difference between D and F Well the distance between those two is going to be two now that we have this we kind of don't even have to think about like the original string so just this is kind of the more simple way to think about it at least for now so now consider this let's just go through every single substring so this sub string has a cost of one so of course we can stay within our budget this substring has a cost of two we can stay within our budget this substring has a cost of three we can again stay within our budget this is the longest string so far by the way right like the length of it is what determines the result that we want to return we're not returning the cost we're returning the length of that string in this example it just happens to be the same then we try the next one this one of length four but the total cost of that is five right we're getting the cost by taking the summation of these values so this one doesn't work and pretty much like even if there were additional values here 1 2 3 whatever we're not going to find any substring starting from here that is now going to be valid because all these values are going to be positive or maybe they're going to be zero but basically if this one is not valid nothing bigger than that is going to be valid then we would continue our Brute Force now let's get all substrings starting from here so this one this one this one and we'd keep doing that you might kind of notice that there is a bit of repeated work here while the solution this Brute Force solution does work it's going to be o of n^2 cuz that's roughly how many substrings there are going to be here but like I said by the time we got here we know this is invalid right so why do we decide to start back here from the beginning and then try to build longer substrings when we don't need to we already found one of size three we tried one of size four it didn't work out for us how about we just shift from the left how about we take that shortcut and now consider this substring the reason we skipped this one and this one is because even if those two were valid they would never be the result we already found one of size three now we're trying to find another one and we're trying to shift from the left as little as we can to make our window valid so at this point if you're familiar with what a sliding window is you probably are convinced that that is the solution to this problem which it is so that's how we're going to solve this problem from here what we would do is shift left here so now we're going to be here this is still invalid though we're going to keep track of what the total cost is right now it's four again we're going to shift left and we're going to decrement whatever value we removed from the current window so now our cost is three this window is valid but it's smaller than the pre window that we were looking at of size three and at this point we're going to try to increase our window now cuz we are within the budget it could be possible there are some zeros over here but there's not so we pretty much have exhausted every possibility so this is the linear time approach now if we create an array like this and we just ignore the two input arrays it works but it's extra space it's linear space so we actually don't need to do this I just showed it this way because that's kind of a simpler way to visualize it we will actually be computing these values on the Fly which is really easy to do just by taking the asy values of these and just taking the difference between them and then getting the absolute value between the difference I think that will make more sense in the code and that will make this a constant space solution let's code it up the main thing here is first of all keeping track of like the current total cost I'm going to have a variable for that I want to make it like this I want to spell it like snake case but that's going to be inconsistent with what the parameter is so I'm just going to do it this way and I'm going to declare our left pointer so this is going to be kind of like the window I was showing you earlier I know I'm not like entirely introducing to what the sliding window is I have plenty of videos on that though and I have like a course that goes pretty in depth on that as well lastly we know that the result we're trying to return is what the largest window actually is the largest substring that we can replace so that is what we're going to try to maximize that's what we're going to end up returning so now let's say for our right pointer in in the range of every position in the input string both of them are the same length so we can do either one here and what we want to do like I said is compute the cost on the Fly what is the cost of this current position that we're adding to our window well let's get the asky value of one of the characters from one string s at index R and let's get the asky value from the other string T at index R same position in both strings though and or it is just how you get the asky value we don't know if this is positive or negative so let's just get the absolute value let's call this the cost and this is what we're going to end up adding to the current cost I guess we actually don't need a different variable so let's just take this and add it to the current cost okay now it could be possible well what we want to do we want to maximize the result right let's assume our window is valid this is what we would do we would set result equal to the max of itself or the current window size size we can compute that by taking the right pointer minus the left pointer plus 1 this is how you compute the size of a substring with the two end points so this is what we would do if our window is valid but it's possible our window could be invalid by adding this new character how do we make it valid again well first of all how do we know if it's invalid it would only be invalid if the current cost is greater than the Max cost if they're equal that's actually perfectly fine but if the current cost is greater that's a problem while this is the case because it might take us multiple characters to remove to make the cost valid so while this is the case we are going to shift the left pointer we're going to increment the left pointer by one but we don't want this Loop to run infinitely so before we actually increment the left pointer let's subtract from the current cost the cost of that character which again we can just compute on the Fly I'm going to copy and paste this part over here but remember we're not removing the right character we're removing the left character so let's change these pointers to left here and left there so believe it or not this is the entire code I'll run it to show you that it works and you can see it works it's pretty efficient in case you're not convinced that this is linear time some people say well you have nested Loops that must mean it's n s no because our right pointer is going to iterate over the entire size of the input our left pointer is also going to iterate in the worst case through the entire string it's not like we're resetting the left pointer back to zero every single time down here if I put left is equal to zero every single time then maybe it would be n s but we're not resetting it so this is not N squared if you found this helpful check out N.O thanks for watching and I'll see you soon