Minimum Changes To Make Alternating Binary String - Leetcode 1758 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum changes to make alternating binary string another easy problem for us today we're given a string s which consists only of zeros and ones so it's a binary string and we want to make it such that it is alternating which means that every other character is going to be different so it's going to be 0 1 0 1 or it could be 1 0 1 0 so already we kind of notice that there's really only two possibilities so even if we were trying to Brute Force this it wouldn't really be an inefficient solution so if we're given a string like this 0 1 0 0 to make it alternating we have pretty much two choices we can either turn it into this or this so we can kind of just look let's first consider if we were to change it into this string well this is different we'd have to swap this to a one these are different we'd have to swap this to a zero these are also different so we'd have to swap three characters these are the same so we don't do anything with that one so we'd have to swap three characters to turn it into this string now what about the other string up here well these are the same don't have to do anything these are the same and these are the same we'd only have to swap this and this well not both of them we'd only have to swap this one into this okay so thinking of it in this way you could probably code up the solution with one Loop or if you wanted to do it a simple way you could even have two Loops one to check for this and one to check for the other but did you kind of notice something when we were going through this for the first string if we were to make it alternating like this we'd have to swap these three characters if we were to make it the other string we'd only have to swap this one that's not a coincidence because notice that these two strings are are the literal opposites of each other this is opposite this is opposite this is opposite and this is opposite so in other words what I'm trying to say is if we only check how many operations does it take for us to turn this string into this string for example like if it's starting with zero how many operations would it take we found it only takes one operation now we want to ask how many operations does it take for this other string to turn it into this other string well we already know that it's going to be all the other characters in other words the length of this is four it's going to be four minus one character that we had to swap so it's going to be three characters for this other string that's a pretty small optimization so it's kind of just taking this from a two pass solution into a one pass solution depending on how you cat it up I think you could cat up into one pass even if you were checking for both of these strings but it's just a slight optimization it's not a huge deal I just thought it was worth mentioning because this problem is pretty easy anyway if you can code up the clever solution I'm about to show you right now you can probably code up the easier one as well in terms of time complexity it's going to be big of of n we do have to scan through every character in the string but no extra space complexity that is going to be constant let's code this up so I'm going to have a variable which is Count it's going to be zero and this is going to be the number of operations if s were to start with zero and then when we return the result we're not necessarily going to return this count what we would actually return is the minimum of this count and the other count which is going to be the length of the string minus this count because that tells us how many operations if s were to start with one so this is the return value only thing left for us to do now is actually compute the count the easiest way to do it is one just iterate over the string obviously but to check if the character at s of I should be a zero or a one we could figure out a way to compare this to like the previous character or the next character but the easiest way is knowing that at index zero we expect the value to be zero at index one we expect the value to be one at index two we expect the value to be zero etc etc the pattern here is that for even indices we expect zero for odd indices we expect a one so that's what I'm going to use that's the Assumption I'm making so for us to check first of all is this index even or odd modding I by 2 this tells us it's odd in the else case we know the index is even now that we know that we know that at an odd index we expect the value to be a one so if the value is not one if it's actually equal to zero then we know we should increment the count by one cuz we have to perform an operation here I could put this in like an if statement uh increment this by one but if you want to get kind of clever you can combine these into like a Turner operator so I'm going to do this and in the else here we'd add zero so it's again not like a big deal you don't have to write it this way if you don't want to I'm just kind of used to doing it this way and in the El case we're going to do pretty much the opposite here so we'll add one we have to make an operation if we were expecting a zero but the character was actually a one so this is the entire code let's run it to make sure that it works and as you can see on the left yes it does and it's pretty efficient if you found this helpful please like And subscribe if you're preparing for coding interviews check out NE code. thanks for watching and I'll see you soon