[Music] hello guys welcome back to Tech Dos and in this video we will look at maximum difference between even and odd frequency two problem which is from lead code number 345 in this case uh if you have already solved range sum query mutable then you will know about how to find the range sum query if you haven't solved it then you can find the link in the description below and you can also consider solving this after having solved this current problem now in this case you are given a string S and an integer K your task is to find the maximum difference between the frequency of two characters frequency of A minus frequency of B in a substring subs of S such that subs has a size of at least K the character A has an odd frequency in subs character B has an even frequency in subs and we need to return the maximum difference between the frequency of a minus frequency of b and we should note that subs can contain more than two distinct characters so in this case once you know that uh you are given a certain size of let's say string or an array string is an array of characters right if you are given a certain size of array and if you are talking about maintaining certain condition in such a way that the subarray size must be at least k that means the size must be greater than equals to k then you should note that you are asked about maintaining a window or you can say that a subarray in such a way that you can actually make this window elastic you can increase the size you can decrease the size but the decreased size must never go below K so this is the case of variable size window variable window size because it is saying about at least k so the window size can be k + 1 and so on till n right where you can have the entire array as one of the windows so it is not just saying about one window size but the minimum window size is k so that means it is saying about a variable window and if you want to parse through a window from one end to the other end of variable size then you know that you have to maintain two pointer L and R where if you make R go to the right hand side then you are increasing the size of the window whereas if you make the L go to the right hand side then you are decreasing the size of the window right so you can maintain variable size window by using the twopointer technique twopointer plus sliding window okay so when you do sliding window then you can uh you can have two types you can have variable size or you can have fixed size sliding window in the variable size sliding window uh you have to use two pointer to maintain the boundaries of the window right so as soon as this it says about substring subs of uh of the string s which is having at least size k your uh mind should think about a variable size sliding window using two pointer right so this is pretty obvious now whenever you have picked a window within that there will be a certain frequency of A and certain frequency of B and whatever is the difference you have to maximize this difference you have to maximize this difference okay now if you consider the values of A and B let's look at the constraint first so if you look at the values of A and B you have exactly five digits into consideration so you have digit 0 1 2 3 4 okay so if you create pairings of a comm b then you can take a to be zero and then b can be taken from 1 to 4 you can take a to be 1 and then b can be taken as zero or 2 or 3 or four because you will not take the same numbers right it is not uh taken as the same number a and b are different so for zero you can pair it up with four possible numbers 1 2 3 4 and similarly for one you can pair it up with four possible numbers which is 0 2 3 4 and so on the same will go for 2 3 4 so each of the digit can be paired with four options and therefore since there are five digits you will have 20 pairs possible 20 pairs possible right now if you know the standard sliding window then a standard sliding window is order of an approach to actually parse the entire array from one end to the other end so if you have already pre-assumed a to be let's say zero and b2 be let's say one then you have created one pairing and for this pairing if you want to find out the window where you have the maximized value of f of a minus f of b according to the problem statement then it will take order of end time so you can try for all possible combination of pairs not just for 0a 1 but also for 0a 2 0a 3 0a 4 1 comma 0 1 comma 2 and so on that means all the 20 pairs and for each of them it will take order of n time so the total runtime in this case is going to be 20 times of order of n and uh the order of n here is 3 * of 10 ^ of 4 so if you look if you multiply these two it will be 6 * of 10 ^ of 5 which is way below your 10 ^ of 8 so this is going to run well within your 1 second if you try to follow the optimal sliding window using the two-pointer approach and trying out with all possible pairings according to the input constraints right so we will be trying to do that the input is generated such that at least one substring has a character with an even frequency and a character with an odd frequency so so if you try to take all possible combinations then at least you will find f of a to have odd frequency and f of b to have even frequency so that at least an answer is possible okay there will be no input where answer will not be possible now in this case the k value is ranging from 1 to s do.length that means the window size will always be within the size of the entire string now if you look at the example given then in this case in the first example you have 1 2 2 3 3 and the k value is four that means the window size must be four so if you look at the indices 0 1 2 3 4 now if I take a to be 1 and b to be 2 then what is f of a that means the frequency of a you have to also select a window right let's select a window from 0 to 3 let's select a window from 0 to 3 so here the frequency of uh a is one that means a was considered one so one's frequency is one f of b that means the frequency of two is also two here so this frequency must be odd and yes it is correct this frequency must be even and yes this is correct so what is the value of f of a minus f of b that you get for this particular window size for the assumed pair of 1 2 in this case you get 1 - 2 which is minus1 okay now if you take any other any other window you cannot take a window size of less than four if you take any other window like let's take a window from 1 to 4 and uh for this a and b value being 1 and two find out the frequency of a it is going to be zero and frequency of b which is going to be two so this is even and this is fine but this is this is not odd this is not odd it is zero so this means this is an invalid window isn't it so accordingly you can keep checking for all the pairings all the 20 pairings right and you will find that minus1 is the maximum value that you could get and that is why minus1 is the answer again uh you can look at the other examples as well in the second example you have 1 1 2 2 1 1 with the k value being three so in this case the answer is one and how did you get one if you take you know the a value to be two and the b value uh to be 1 then in this case if you if you select this window 0 1 2 3 4 5 6 so if you select the window from 0 to 4 is it a valid window size yes this window size is five which is greater than equals to 3 so this is a valid size-wise it is correct let's see count wise so the frequency of a where a is 2 is equals to three and it should be odd and yes this is correct if the frequency of b which is assumed to be one in this window the frequency of one is two which which must be even and yes this is correct so that means the frequency of a and b being odd and even it is correct the the the size was also greater than equals to k so this is a valid window now in this case you can calculate f of a minus f of b which is 3 - 2 it is 1 okay now we got one in this window and if you calculate across all the window sizes all the valid windows then you will not get any value greater than one and that is why one is the answer right so I think you have got the idea of this entire problem so once you have understood uh that we are going to solve by sliding window two pointer approach then let's see how to apply the sliding window now I have taken an example with 12 elements and here k value will be three so for the odd even combo I'm taking a to be two and b to be 1 so I will find the frequency of two and frequency of one frequency of two must be odd and the frequency of one must be even our goal is to maximize f of a minus f of b that we already know from the problem statement and if we apply the sliding window to pointer then the right pointer will start at index zero left pointer starts at index zero in general sliding window approach we move the right pointer to the right hand side and we have to define a stopping condition right and when right pointer stops then the left pointer moves from left to right hand side and we have to define a stopping condition for that too so the general sliding window rules uh will be defined for when to stop the right pointer when we move from left to right and and the second point is when to stop the left pointer when the left pointer moves from left to right so for the first case for stopping the right pointer we can take a very simple scenario where I say that if the window size is K then I will stop okay size-wise if the window is valid then I will stop that means when I start moving at this point then if r goes to this index two then I will stop because this is a size three and this is valid this is valid size okay because the size must be greater than equals to three we will stop we are trying to keep it simple uh for the time being now when should the left be stopping let's say that we will just move the left one time to the right hand side in such a way that the zero element will be lost in this case and if this element is lost then we have to decrease its frequency now the zeroth element is zero here if it matches with any of the A or B the frequency of A or B will get decremented but if if it do not match with any of the A or B according to what combination we have taken then it will not be affecting uh you know the frequency and you can simply move the left pointer to the right hand side so you need to keep a track of whichever element you are losing is it affecting the frequency then you update the frequency right so I think uh this simple approach is clear but the problem in this simple approach is you are not maintaining variable window size but you are only maintaining the k window size so when r stops as soon as you reach to r minus l + 1 greater than equals to k then the window size is exactly k okay and then the L pointer moves to the right then in the next iteration the R will stop at three then the next time L will move to two and R will move to four and so on so in this case we are not covering all the cases we are covering the cases where the window size is exactly K but not greater than K okay so this will give you correct answer only for certain scenarios where the answer is contained in the K size window but if the answer is contained in a window size greater than K then it will give you wrong answer isn't it so our problem here is that we are not able to check for a higher window size than K because of the simple rules so we need to do certain kind of modification or the rule or otherwise we need to apply the two pointer in a different way so let's see how to apply it let's say that my right pointer is present at certain point and uh I am assuming it to be present at let's say 10 now our assumed combo in this case is a to b2 where frequency of a must be odd to make a window valid b is one that means frequency of one must be even to make a window valid and the size wise the window size must be greater than equals to three okay once we have known this then if the right pointer is at 10 then where will you place the left pointer now since you know that the window size can be greater than equals to k therefore at least it should be k so the left pointer can be placed either at 8 or at any index ranging from 0 to 8 isn't it any index ranging from 0 to 8 it cannot just be 8 it can be any index so now which index will you choose it is up to us to choose whatever index we want so we will choose a certain index in such a way that let's say uh I I tell you that let's choose this index then this index will only be chosen if in the middle the count of the frequency of a is odd first of all then the count of frequency of B is even and in such a way that f of A minus F of B is maximized it is maximized if all these conditions are followed along with the size being greater than equals to K if all these conditions are uh followed that will be the optimal position of L that will be the optimal position of L okay so since I know that f of a minus f of b have to be maximized you know f of a minus f of b have to be maximized so if this entirely has to be maximized then you can also look at the separate components and say that if f of a can be increased then this will be maximized or if f of b can be decreased then this will be maximized or if both of them can be parallelly increased and decreased then it will be maximized right so you can break down the goal saying that I will minimize f of b or I will maximize f of a so I have to place the left pointer according to uh where it this optimal point is hit because L is just one pointer right we do not have two pointer it is just a one pointer so I have to check a balance between uh B and A frequency okay so where to place it now let's say that I chose to place this L here then how to find like uh what is the frequency of uh A and B in the middle so what I will do is uh if you had placed L here then I can iterate and find the frequency of 2 and that is equals to 5 yes it is odd and I will I will iterate and find the frequency of 1 it is 2 and yes it is even and I can find the difference between them 5 - 2 it is three so the value that you get here is three if you try across all windows then you have to try to maximize this value this type of value right now how much time did it take if I if I uh selected this.3 then it will take order of end time that means all the items could have been in the middle right so it will take order of n time to uh calculate what is the value of f of a minus f of b so that has to be tried for all the indices from 0 to 8 isn't it that has to be tried repeated for all the indices but instead of repeating it what we are maintaining is count in a range so if you think about if L was present at three what I was interested in count of two count of two in the range of 3 to 10 if you think of count of range uh two in the range of 3 to 10 how to get it more optimally then you should think about the prefix sum you should think about prefix sum maintaining the count of two at any particular index isn't it at any particular index so if I apply the prefix sum for the count of two I can say that count of two is zero at here 0 0 first time so first count two count three count three count three count four count four count five count and you can say here it will be five and similarly if I can maintain the prefix count for you know this is for A if I can maintain prefix count for B which is one so here zero count one count two count 2 2 3 count 3 3 4 count four this is five count isn't it so if I can maintain here and if I have to now check how many items are in the middle like let's say I said about placing L here right L at this point then you want to check like how many how many you know count of items A and B are present in the middle so you know that R is present at this 10 at this point and L is present at this point then you can easily calculate it easily you can calculate it you can get d f of a minus f of b by simply subtracting this value this value difference with this value difference why is this happening because 5 - 4 equals to 1 is giving you f of a minus f of b in the range of 0 to 10 in the range of 0 to 10 okay and if you think about what is 1 - 2 giving you 1 - 2 = to -1 is giving you the f of a minus f of b in the range of 0 to 3 isn't it so if you subtract these values like if you subtract 1 with minus1 it becomes 2 this means that you are getting the result in the range of 4 to 10 but what I'm interested in is getting from 3 to 10 not from 4 to 10 so that is why I will be subtracting f of a f of b in the range of not 0 to 3 but 0 to 2 so that means I have to look at the previous value so this value right not 1 comma uh 2 but 0a 2 so if you subtract 0 with 2 then this will be minus2 if you subtract five from four it will be 1 so if you subtract 1 with minus2 then this is going to be three that means the f of a minus f of b value is going to be three in the range of 3 to 10 it is just the same concept as the prefix sum range sum query and that is why I asked you to solve that problem range sum query immutable which is simply solved by using the prefix sum technique right so I think you have figured out that we will be using the prefix sum in this case along with the uh sliding window to pointer technique okay so I have taken the same example and I have created prefix sum a of size n + one where n is the number of items which is the string size in the in the beginning and prefix sum b which is of the same size i had also assumed a to be two and b to be one okay now in this case if you see prefix sum a size is one extra because you know that if you want to find range sum in the range of L to R then you can also take just prefix sum at R minus prefix sum at L minus one and you don't have to worry the uh worry about the case for the boundary boundary condition where L minus one goes to an index less than zero okay in order to compensate for that I will be appending one extra item on the left hand side okay so that is this is just a dummy item it will always start from zero fine so this is how I have created prefix sum A prefix sum B now in this case in in the previous example I had showed that R was already present at index 10 so if you make R go to index 10 R go to index 10 then where will L go you know that K value is equals to 3 so L can go anywhere in the range of 0 to 8 l can go anywhere so again uh we may have to try out all the all the indices isn't it so we may have to have L here that means at index number zero and try to find out the value of f of a minus f of b which is done by taking at 10 what is the difference between this 5 - 4 5 - 4 which is 1 and take this one and subtract it with the l - 1 value that means 0 - 0 which is 0 that means the difference between the count of 2's and ones will be 1 you check it out 1 2 3 4 5 2's and 1 2 3 4 1's right so this is how it is done now if you check out okay this is how you can calculated f of a minus f of b and you have to parse this l for the entire range from 0 to r minus k + 1 but if you think about the validity check how do you maintain that it is a valid window you have to also check for that isn't it so if you are present at any particular index like let's say you are present at this index L then in this range from 4 to 10 the count of twos may not be odd may not be odd it must be odd in order for the validity to happen okay whatever a you have assumed you cannot have even count of it in the window so 4 to 10 is not a valid window so no need to uh calculate the subtraction value isn't it so that we need to take care of i will show you how to take care of that but before this for any particular R index since your L is moving from 0 to R minus K + 1 for every R point you are taking order of N time so for all the N number of R points your algorithm is going to run in N square time even after taking the prefix sum we have not improved our solution okay n² is not going to solve our problem we have to solve it in order of n now how to how to uh select the optimal l value in just one step having to do two things the first thing is the validity that means whatever l value I point to it must be valid valid in terms of valid in terms of size and valid in terms of f of a being odd count and f of b being even count these three things have to be taken care whenever I point L somewhere and also the second thing should be it should be optimal that means wherever I make L.2 in the range of L to R that f of A minus F of B must be maximized maximized for all start points ending at R okay for all the starts points and ending with R so if I say that L will point to four and this will give me the optimal result when R is at 10 then this must be giving the maximum value of F of A minus F of B when I try out L for all the options from 0 to 8 okay this should be giving you the maximum one so that is why these two conditions have to be taken care and I have to take care of these conditions in O1 time only if you take care of this in one time you can make an optimal choice for every R index in order of one time and hence your algorithm will change to an order of sliding window algorithm right so first let's see like how to how to choose uh I mean how to take care of odd even because you already know how to take care of size isn't it if r is the index then you can go from 0 to r minus k + 1 this is how you take care of size let's see how to take care of the odd even index now for that to happen let's say that your r pointer is at 10 so my range is going to be from 0 to 8 now if you look at this uh index 10 then what is the meaning of this five the meaning of this five is my a was two and my b was actually you know one so the meaning of this five is the frequency of a is actually five right from the beginning from beginning means from index zero the frequency of a is five the four here means that the frequency of b is equals to four so what is what is this a must be odd and B must be even okay initially they can be anything right they can be anything they could be odd or even it does not matter so in this case it is five which is odd and frequency of B is even now where I should place this L so I should place this L in such a way that the count of A that means the frequency of A in this range from L to R must come out to be odd and the count of B in this range of uh L to R must come out to be even so if let's say in this in this particular scenario if let's say that uh the count of a was five which was already odd and you want to subtract it with some another count of a let's say f a dash okay so f a is is let's say from the beginning it is it is till the end and fa dash is from the beginning till l minus one index so if you want to subtract them this is an odd count okay the final in the middle is something that you are finding you have to get it odd count then what should be the count of this f of a dash it must be even because odd minus even will only give you odd if f of a dash is odd then this is not going to work isn't it so based on that I can tell you that uh if you know this rule it will be very helpful otherwise you can just go through it even minus even is always even minus odd is odd odd minus even is odd and odd minus odd is even if you know this rule then according to that I have made the statement that if f of a dash is even then only you can place this cell at index three otherwise you cannot and for the same reason f of b is four which is even the final uh count of b must be even so if you subtract even from even you always get even otherwise if you subtract odd from it then you get odd so that means f of bdash which is the frequency from the beginning till l minus one must be even otherwise this l index at three is not going to work out right so again I can generalize this entire thing and I can say that if your right pointer is present at r where f of a is the count of uh a from beginning from zero till this index r which is x x is the count and f of b is y that means the count of element b from index zero to r is y then I can uh then I can just compare it with an L pointer where you want to place so that from zero to the previous value of L pointer if you get F A to be P and FB dash to be Q then in between in between uh you you have to get X minus P to be odd for sure and Y minus Q to be even for sure because the f of A in the middle in the middle must be odd and the f of b in the middle must be even this is according to the problem statement isn't it so if if now I say that x is odd then you can look look at this chart and simply you can say that if on the left side you have odd then these two cases will hit and if if on the right side you have odd then only this case is going to hit right so if this is odd and the and the third one is odd the second value must be even that means the p value must be even if this is odd then this will be even okay and similarly if this is even then this has to be odd you see even minus odd is odd similarly for this B if this is if this is even this has to be even if this is odd then this has to be odd because even minus even is even odd minus odd is even minus even is even and odd minus odd is even right so according to that there will be four states that we will have to manage four states so given a combo P comma Q q in this case I have taken a comma b as the combo right so if you have taken P comma Q as the combo then for that either this P is even and Q is even or P is even and Q is odd or P is odd and Q is even or P is uh odd and Q is also odd so there will be four states even even odd odd even odd odd if I can represent this using two bits two bits in such a way that even I will represent by zero and odd I will represent by one then even even will be represented by 0 0 in binary and that will be represented by a value zero in decimal number system similarly even odd will be represented by 01 in binary which will be value 1 odd even will be represented by 1 zero in binary which will be represented by a value two and uh odd odd will be represented by 1 one in binary which will be represented by value three isn't it so this is how I will be representing the four states and that is why I have taken 0 1 2 3 okay I hope this is clear therefore while solving the problem we must consider what is the state of XY if x is let's say in this case even and y is odd then the state is going to be 01 in binary that means uh one the state is one so what we are looking at as the target on the left hand side as the target on the left hand side if this is odd then the left left hand side as well you are looking at odd if this is even then you are looking at even right but if you look at a's frequency it is flipping it is flipping so If you see here if you have even you are looking for odd on the left side isn't it and if this is odd then you are looking for even on the left side so the parity is flipping for a whereas the parity remains the same for B so that means if X is even and Y is odd i'm just considering an example even odd then what we are targeting on the left hand side for PQ's parity is E will be flipped so so this will become odd odd will not flip it will remain as odd so we are looking at O that means odd odd for P and Q as a parity so this parity will actually take care of about uh the four cases that we had seen previously right so I I was showing you about this odd even cases the parity will take care of it the size will be taken care of by us and now it comes to the optimal uh check so for the optimal check you can say that if I have an R then I will put an L like I will choose an index L in such a way that whatever is the diff value here and whatever is the diff value at this point if you just subtract them then that should be maximized okay because that will give me in between the value for f of a minus f of b according to the range sum query prefix sum technique isn't it that is what we are trying to apply now if you look at validity case we have one more case uh the case is whenever you select a a subarray then the frequency of a must be greater than zero and frequency of b also must be greater than zero that must be true these two things must be true so if you choose a subarray like let's say uh you have chosen certain subarray like uh if I can pick this one okay this one as your R and if you pick this one as your L then will this be valid if you look at these two values are same this means in between in between to the right hand side in between there is no occurrence of B there is no occurrence of B so if there is no occurrence of B then simply uh this is not a valid window right this is not a valid window now I will only be checking for B i will not be checking for A because on B side if this is having even parity I will be searching for even parity on the left and even if you don't have any items in the middle you will find the same parity okay but on the a case it will not be true if here you have an odd parity you will be searching for an even parity so the so the parity flip cannot happen without an element parity flip cannot happen without an element because if I say that you are taking mod 2 and that will give you a value either zero or one either zero or one and here you have a value n then if n mod 2 was let's say zero and you require one now then n mod 2 will never give you one it cannot give you two different values with the same mod isn't it with the same n value so it must be n + one or n + 3 or somewhat a different value than n otherwise it will not give you a different parity right i will not be uh checking for the equality but for b I will check for the equality because the parity is same and same parity can occur even without occurrence of the numbers okay but the last question which still remains is how we are going to optimize it we have we have seen everything about validity all the four points but what about the optimality so for optimality we will be taking two arrays one will be the min value array so min value array will be of four size which will be covering all the cases even even uh even odd then odd even and then odd odd so this will be containing when you are sweeping from one side to the other side from left to right when you are sweeping the L pointer when it is sweeping then what is the minimum value of F A minus FB dash that you have seen where A dash and B dash I'm saying that A dash and B dash are the same as A and B i'm just trying to differentiate them based on L being the end point or R being the endpoint right if R is the endpoint I'm using A and B if L is the end point then I'm taking A dash and B dash right so uh it will contain the minimum values minimum value of F A -ash minus FB dash in the range of 0 to N minus K + 1 so that when you have to pick a optimal L for any value R on the left hand side if you want to pick an optimal L if the parity here is odd even then you will be going to find even even right on the left hand side so even even is zero you can go to this zero and look at the min value and you can simply return the minimum value of FA minus FB dash right so this will be done in just order of one time now if you have not understood this then I will be showing you in the dry run how to maintain that okay so let's look at the dry run in this case I'm taking 12 items and I will be doing this just for one combination 2a 1 where two is our a value which must have odd frequency and one is our b value which must have even frequency right now if you look I have already premputed the prefix sum a prefix sum b and I have taken a min value of size four covering all the four states so when we sweep from left to right if my r value is here and my k value is let's say equals to 3 then it will contain all the minimum values in the range of uh n minus k + 1 okay so n minus k + 1 is 7 but I will be maintaining till l minus one index right so that is why I'm pointing to six and not seven so I hope it is clear what we are trying to do so in this case I will be assuming the K value to be three k value equals to three right and we will be doing a dry run now the minimum index will tell you wherever the minimum occurred what is the index of it okay why it is important it is important so that you can m you can match the beast's frequency if the B's cumulative count is same then that means in the middle there is no count of B occurring and that is how you can identify the invalid case okay so I'll show you in the diagram how to how to do this now before starting since I want to calculate the maximum difference of FA minus FB f of a minus f of b so that's why I'm taking a max difference variable defined to minus infinity okay and here uh the base case which I will be considering is min value at zero will be zero min index at zero will be zero why is this because this is the condition when your l is pointing to zero and r is pointing somewhere and you are including everything so if you are including everything then you are not excluding anything because this prefix sum is actually counting from left to right for for the items that you are excluding on the left hand side isn't it so you are not excluding anything so you will be having zero or you can say you are not including anything at zero you don't have any value right so initially I will be starting with a min value of zero for the even case and it is occurring at index zero that's what I will assume so let's start at index three now index three means that index two index two uh in the original array right now if you see this index the parity on the a sum and the b sum is even and even Now if you find out the left side target then the parity as I explained for this a will be flipping to odd and the parity of the second one will remain to be same which is odd even if you go to odd even it is saying infinity which means that there is no valid left pointer okay there is no valid left index which can be chosen in such a way that L2R will be maintaining the frequency of A to be odd frequency of B to be even the size is also uh I mean K and all those conditions are satisfied right it will not be satisfied that means we cannot maintain the frequency of A and B to be odd and even and that is true you can check it out it is true right if you check this array the frequency of a which is 2 is zero that means a is not occurring both of them must occur right they are not occurring so this is not valid so we have to move to the right hand side but before moving to the right hand side we have to account for this one this has to be saved in our min value because now our L will be ranging with this zero right once the r moves to the right hand side then my range from 0 to n minus k + 1 and to the left of it so I will be subtracting one more because if I want to get the items in the middle from l to r then I have to take from 0 to l minus one right so it is n minus k + 1 minus one so now when R is sliding to the right then this information has to be updated into the min value because the min value will try to track case by case all the all the FA minus FB minimum values so let's see at this at this uh index one zero means index one here right because this zero is dummy here so this uh one is having even parity even parity okay so this is the case for even even and now the difference between then FA minus FB is zero okay so at even even it is already zero so we are not able to minimize it so let it be there okay and now we are uh calculating for this four we are calculating for four at four what is the parity odd even so odd even is the parity so that means on the left side we want even even so if you look at even even do I have infinity or some integer value yes we have an integer value so it is occurring at index zero right it is occurring at index zero so if you look at uh the count here at index zero the count of B is zero and at this particular point it is two that means B is occurring we will not be checking for if a is occurring because if the if the uh state is flipping then that means it must have occurred in the middle right so that means we have a valid L on the left hand side and that L will be at zero only so if we place R R here then yes we can place L at zero in such a way that in the middle the frequency of two the frequency of two is going to be one which is odd and the frequency of one is going to be two which is even and uh so it is possible to place at zero right and that is what this is saying that zero is the optimal point where I should place and how to get the value so you already know FA minus FB from 0 to l minus one and that is going to be zero here and at this particular point four you can subtract one with 2 so that will be how much 1 with 2 will give you minus1 so if you if you take minus1 and subtract from zero it is going to be minus1 only right so the difference is going to be minus1 now the max difference is minus infinity so minus1 is better answer so update it okay minus1 is better answer we have updated it fine now uh we have to move forward before moving forward you have to save this into the min value let's let's see what is the state it is even odd even odd so look at this even odd okay and see the value what the value is coming 0 minus one which is minus one so minus one is actually a smaller value we want to minimize the option for each of the state so this is minus one at which index it is occurring at index two so update this to index two okay and now we will be moving forward to index five five means four here okay now at five you check the parity is even even so what parity I want on the left side odd even so if you look at odd even it is infinity that means there is no option on the left hand side if there is no option then that means uh you cannot form a valid window if you have r here so what we have to do we have to move to the right hand side but before moving we have to save this information because the range of options for L is increasing right so this option has to be saved so this is uh 02 that means even even state is even even right so look at this even even and what is the value 0 minus 2 so this is coming out to be minus2 so let's update it at which index it came it came at three so update the index to be three and move forward even though you will see that uh sometimes I will not be comparing the frequency of B but that has to be always compared okay when we when we are at six uh the uh parity is odd even so the parity here is odd even so that means on the left hand side we want even even okay on the left hand side so where is even even occurring uh even even okay it is not infinity so that means it is valid even even is occurring at index 3 so let's look at index three this value is two here where we are present at six this value is also two that means B's frequency has not occurred in the middle so this is not valid okay this is not valid so we need to move forward before moving forward I have to save this into the min value what is the parity odd even odd even is the parity look at odd even this is infinity so I can improve it by doing 1 minus 2 which is minus one and this is happening at index four so save index four here and now I will be moving to index 7 okay index 7 so at index 7 um if you see this parity is ordered parity is ordered and then I will be making uh a requirement for even odd parity on the left side so let's look at even odd parity this is present this is not infinity okay and this even odd parity is present at index two so go to this index two and check this value one and this value is three that means frequency of B is not zero in the middle it is greater than zero so it is fine so that means this is a valid option to be taken this is the optimal option where you can place L right it is saying two that means you can place at one this is saying seven so you can place R here at six so what will be the value f F A minus FB in the middle it is 3 - 3 which is 0 minus whatever is whatever is the value here which is basically 0 - 1 right so it is minus one so 0 - -1 is going to be 1 okay 1 so I want to maximize the difference so one is better than minus one so update it update it okay so I think uh the things are getting clear for you now let's move forward before moving forward I have to save this state so this is even even so go to this even even and check the value 2 - 2 is zero already I have a lower value so don't update anything go to eight parity check the parity odd odd so this parity is odd odd what is the requirement on the left side even odd look at even odd it is saying a non- infinite value that means even odd parity is present and this is present at index two check the frequency value here one here the value is three that means b is present in the middle okay now you have to uh see the values the value is is minus one here the difference value is going to be zero so 0 -1 is going to be 1 and this max difference value is already one so no update is going to happen now before sliding you update this which is odd even parity so odd even parity what is the value 3 - 2 which is one this is already minus one lower value so don't update it move to the right hand side 9 now at this point you have even odd parity even odd parity so on the left hand side you need odd odd parity so look at this odd odd value it is infinity that means there is no left side good option for you okay so what you need to do you need to just move to the right hand side but before moving you need to add this value okay the information into the min value so this is ordered parity so for odd parity the value is 3 - 3 0 so this will be updated to zero and it happened at index 7 so save it okay now you slide to the right hand side now here uh at 10 you have even even parity that means on the left you need odd even parity okay odd even parity so look at odd even parity this is minus 1 what is the value here uh 4 - 4 0 right but first we have to check the B's frequency this odd even parity is happening at index 4 check the B's frequency yes four is greater than 2 so B has happened and now you can calculate 4 - 4 to be 0 minus and then this minus one value this is going to be one so already max difference is one so no update is going to happen before moving to the right hand side update this information this is ordered parity so for ordered parity uh you are getting 3 - 3 0 this value is already zero so no update now you move to the right hand side this is index 11 here you have odd even parity odd even parity so on the left hand side you need even even parity look at even even parity it is saying minus2 that means it is valid and it is present at index three go to index three compare the B frequency 2 with four four is larger so B has occurred yes now you can calculate 5 - 4 is 1 minus for even event even you have minus2 so minus 2 so that is going to be 3 so that means three is larger so update the max diff value to three okay and now before moving to the right update this information so this is even odd parity even odd parity so look at even odd par and the value is 4 - 3 1 but this is already a lower value minus 1 so no update is going to happen okay now you move to index 12 here you have odd odd parity so on the left hand side you need even odd parity look at even odd parity this is minus one that means there is an even odd parity which is valid so the index is two go to this index two look at the frequency here it is 1 here it is five so five is greater than one so yes b has occurred in the middle now you can calculate 5 - 5 is 0 minus I mean it was even odd parity right so it will be minus one so this is going to be one but already max diff is three so no update is going to happen and we are done so once we are done the max diff was actually tracking the maximum value of frequency of a minus frequency of b okay and the parser which was going from index k to index n is actually your r value and whatever this min index is giving is all your l value which is following all the validity conditions and we are we are doing it optimally in one time so if you follow this dry run then this entire approach is going to be order of n for each combination and there are 20 combinations so 20 * n is also order of n that's what I will be assuming but let's say that if you have m unique letters instead of just five letters then in that case the number of combinations that you can form is m²ared and so I can say that I will be taking n into m² time complexity now the space complexity is order of n in this case but if m value can be very large then I will write it as n + m but in this case it is just five so I have just ignored it okay so I hope this entire approach is clear let's now look at the code if you are someone who is looking to prepare for top product based company within a limited time of just 3 months then we have brought for you both the DSA and the system design live interview training program the most important feature of this program is you get a filtered and condensed structured curriculum in-depth discussion of all the topics and my guarantee of your understanding one-on-one guidance with me and live weekend classes to know more about the training you can WhatsApp us on this given number in this problem we are given the string and the k value and uh I will be taking the size of the string and assigning the max diff value to integer minimum that is minus infinity and then we will take two loops to try to create all possible combination of ab where I said it will have 20 combinations right and if a is b uh then this is not a valid combination and I will be skipping it now I will be taking any combination AB and try to calculate the max diff value or you can say the diff value and and we will try to maximize the diff value over all possible 20 combinations and finally I will return the max diff value right that is what I will be doing now I will show you uh you know the steps so if you look at the calculate difference then in this case I take the string as the window size k the a and b which is the current combination now take the size of the entire string and assign the prefix sum A and the prefix sum B which will be maintaining the count of A's and B's at all the indices so if I can just show you that we will move up and you can see the prefix sum A prefix sum B is taken with a string with the size of the string and A and B value which is in the combination so the first value is a dummy value which will be zero and we will be iterating only from index one that is what we will be interested in so in the actual array we will be iterating from 0 to n minus one but in the prefix sum array it will always be i + 1 which will be updated with 1 plus prefix sum at i if the character matches with a okay otherwise we will just copy the same value this means that we are ignoring the rest of the values same goes for b as well so I think you can easily calculate the prefix sum now once it is done once it is done then you know we will be taking the min value of size four so as to maintain the four states even even odd odd even and odd odd okay all the four states min value on the left hand side ranging from index 0 to n minus k + 1 minus one okay and the min index the corresponding value if you if you have minus one value as the minimum value where did it occur at what index did it occur that index has to be saved this is the base case where we start where you can say that we don't include anything on the left hand side that means this part is empty or you can say everything is included on the right hand side now we will be uh trying to iterate and try to maximize the difference value so in this case I'm taking the max diff for this particular combination it will be minus infinity and then iterate for all the r pointers pointing from k to n k to n means in the actual array it will be going from k minus1 to n minus one right in the prefix sum it will be going from k to n so these are the actual r pointers right so for each of the R pointer that means for the end point we will be trying to calculate at this R location what is the parity in the prefix sum A and the prefix sum B so check the parity a parity B you know that if the if for A it is even and for B it is let's say even then on the left hand side you need an odd parity for A and you need an even parity for B that means parity of B will not be changing but for A it will be flipping okay so that is how we are flipping by using the zor operator 0 1 is one and ones or 1 is zero so that is the property we will be using we are left shifting by one time so that parity of b gets appended to the right side so parity of a parity of b where parity of a will be the uh first bit and the parity of b will be the zero bit right so that is how we will be seeing now if min value at the parity is not equals to integer maximum that means it is already uh saying that there is a valid index on the left hand side then I will be checking its B's frequency okay B's frequency if the B's frequency here is X and here also you have X then that means there is no B on the in the middle that is from L to R and so this is not valid otherwise if if this is Y where Y is greater than X then it is valid and so I will be trying to maximize is the difference this we have already seen in the dry run after doing this we will be sliding the start point to the right hand side because if the R pointer is at index I and when I move it to I + 1 then whatever was the L minus one value here which is N minus K + 1 minus one then if I move this R to the right hand side the coverage will also increase by one time right so that coverage has to be added to the min value the min value and the min index array right so that's what we will try to do i will try to find the parity odd even even odd or what it is find the parity now this parity will not be flipped because we are not trying to find any target to the left okay now see the parity and find out the difference between f of a and f of b at this point okay save it in start div and if the start div is minimizing that parity's min value then that will be updated with the new start div and uh the parity will be updating the index as I had shown in the dry run after doing it for all the R indices we will be returning the max div so I hope this entire code is clear you may have to go through this again uh to actually understand it in a better way but this is a difficult type of sliding window algorithm so I will advise you to have some patience and watch the video again if you have missed any of the points i hope this was clear if you still have any doubt then feel free to comment below and I'll try to help you as soon as possible see you guys in the next video