Leetcode Biweekly Contest 187 | Video Solutions - A to D | by Devansh | TLE Eliminators

[00:26:59]Hello. Hello. Hello. Hello. I'm audible folks.

[00:27:07]Hello folks. Am I audible?

[00:27:33]Hello. Hello.

[00:27:39]Yo, folks.

[00:27:57]Let's start, I guess.

[00:28:01]Is my audio clear, folks?

[00:28:06]Is audio Yeah.

[00:28:34]Hello.

[00:28:36]Hello. Hello.

[00:28:41]Yo, folks.

[00:28:48]Hello.

[00:28:51]Hello.

[00:28:55]Hello. Hello.

[00:29:00]Hello.

[00:29:02]Hi. My audible folks.

[00:29:32]Hello. Hello. Hello.

[00:30:38]Hello. Hello.

[00:30:49]Hello.

[00:30:52]I hope now I'm audible folks.

[00:30:56]Yeah, everything is fine.

[00:30:59]I'm literally struggling with my mic from last one hour, believe me.

[00:31:11]Let me check on my phone and let's start.

[00:37:32]Hello.

[00:37:34]Hello. Finally, it works. Yeah.

[00:37:38]Damn. Please tell me my audio is coming and it's good.

[00:37:45]Good to go. Please. Hey chat, is anyone here?

[00:38:00]Hello. Hello. Hello.

[00:38:16]Hello.

[00:38:21]Uh, can we start, folks? Let's start.

[00:38:23]Let's start. Yeah, you are audible.

[00:38:24]Thanks, dude. Literally, I don't know what the hell is wrong with it.

[00:38:31]I literally I'm 50 minutes and I'm just doing hello to me, I guess. No one even heard. Anyways, how was your flip card flip card? I was looping out how many questions you ordered today, folks.

[00:38:51]Doing how many questions are you all dead today folks? You all dead today.

[00:39:02]All I think. Yeah. Yeah. Great dude. Great.

[00:39:07]Anyone else? Uh this was uh Python my SQL tries another hard DSA. Yeah, this was I think you're talking about flip card grid, right?

[00:39:21]What was the finish time? I don't know around 35 minutes or something like that. I was lazy today. I was not that much focused.

[00:39:39]Start from third.

[00:39:56]can't stand transform last. We have a protocol that we need to follow that we have to take care of everyone. Right?

[00:40:02]You are smart. You don't need first and second. There might folks that might have uh you know struggled from first or second and that they might need some gut intuitions behind it. So yeah let's let's discuss it right let's go straight forward because we are already late and we also have one more PCD that will come after on the same channel which uh I think which which will be of code courses right today was code courses let's start from the very first question right let's let's start rearrange string to avoid character pers How was today's contest? By the way, I think today was really easy.

[00:40:57]Today's contest was really easy compared to like past contests. And yeah, like that's all I guess.

[00:41:11]Let's start with the very first problem which is rearrange the string to avoid character pair. You are given a string S and two distinct lowerase letters X and Y.

[00:41:24]Right? Rearrange the character S to construct a new string T. Such that T is a permutation of S and every occurrence of Y occurs before X and Y. And we have to return any valid string that we could get. And a permutation is rearrangement of all the characters in that string.

[00:41:44]Okay, cool.

[00:41:50]Code forces round is also happening today. Yeah, there are actually two contests that are happening simultaneously.

[00:42:43]Yeah.

[00:42:45]So the first question says us that we have two strings. The one is uh we have one string s and we are given two characters x and y. So this is a string and we have two characters x and y.

[00:42:57]These are characters and what we have to do we have to tell we have to rearrange the characters of S to new string T such that T is a permutation of S and every occurrence of Y appears before X in T.

[00:43:14]Basically we have to make this T which is a permutation of S. Permutation means the number of letters that are used in S will be same. Right? For example, a a b and b a a a both are permutations of each other because the number of occurrences of each letter a is twice b is once is same. Third thing, one more condition. This is the first condition.

[00:43:39]The second condition is that every occurrence of y should be before x.

[00:43:46]It should be before character y not the y letter. Right? And let's also see the constraints of the problem. We are given that the size of string is less than equal to 100. So yeah, this is pretty small. Let's say n is the size of string. It's less than equal to 100.

[00:44:05]Right? Let's move forward and let's see using some example.

[00:44:12]Example, let's say we have a a b c and d. Now x is equal to a and y is equal to b. Then we have to make this as S. This is string S. We have to make a string T which is first a permutation.

[00:44:31]Second uh every occurrence of X right which is character A should appear before every occurrence of Y which is character B right. So here you can see that every occurrence of A let's say here also we have A. Now you know that this is before the B character. We only have one B character. This is also before B. But uh sorry, Y should be before X, right?

[00:44:59]My bad. My bad. My bad. My bad. My bad.

[00:45:05]Character Y should be before X.

[00:45:13]Right. So A should be always before B. A is before B. Yeah. A is before BR but this A is after B. So we have to make a permutation like A A A A a A a B D. This works right. We just swap them. Now all the occurrences of A occur before B.

[00:45:29]Yeah, this is good. So what we did here or what what what could be our intuition is we only care about character A and B here which are our character X and Y in general. These are variables not characters, right? Yeah, we only care about them. So can I do this? Can I do this? First print all occurrences of character X then print Y right or we can then print Y otherwise rest of characters rest of characters what does this does by this this ensures that all occurrences of character X right this is a variable here the uh the value of this variable was a so all occurrences of X are in the starting right this is exactly what we needed we we need that X sorry all occurrences of Y really sorry all occurrences of Y are in starting so first we'll print all occurrences of Y and then we are going to print rest of characters right so if because this ensures that Y is in the starting and we want Y to be before X So if I print all the y is in the starting right that means then I print rest of the characters that means this is a permutation right because I'm using same number of characters and also x would be after it right x would be after y let's take an example let's say I have this and here x is equal to b and y = a now what we want we want y before X right here Y is character A and X is character B right so first I'll print all occurrences of character Y of character A or Y that means first I'll print A and then I'm going to print the rest of characters which is BC and then I'm going to print it and this will always be true right so this is our First print all occurrences of y print rest of string.

[00:48:02]Let's see its code.

[00:48:05]This is the code. What I did? I first calculated frequency of all the characters. Right? Then this is my answer. After this is my answer. So I'm first pushing all the Y characters and then I'm basically pushing the rest of characters. What are the rest of characters? Characters which are not Y.

[00:48:23]Right? So here what I'm doing pushing all Y then pushing all rest of characters.

[00:48:35]Right? This is the final solution.

[00:48:38]What's the time complexity for it?

[00:48:42]What would be a time complexity for it?

[00:48:45]time complexity would be of n because we are of n or n login if like I'm storing but yeah here n login because I'm using map otherwise you can even boil it down to of n you can either use vector for this right because the maps because the characters are 26 for each character you can make a vector of 26 uh right and this can become of right and the space complexity is uh of n because we are storing the string right so this is the first question right we will be actually now I'll see codes and comments first you can simply count the number of y and this is right exactly what we did exactly what we did I know you don't you didn't understand then for each number did you solve C how did you do it we are going to discuss C as well uh question two fire submission on question five question fiveish I don't think there is any question five I think you are talking about something else hello you are okay let's move to question number two so we can move to question number three and four which majority are looking for now you are given three inteious here x s n s or Right now, now how can we do it? Yeah. So here you are given three inteious n S and M.

[00:50:29]Question number B, N, S, M, M. These are three inteious in inteious.

[00:50:36]And what we are told we are we are told to find a sequence of inteious m such that sequence zero is s. Okay this is the first one. Second we are told to find a sequence find sequence such that the first element is s. This is the starting element. Cool. And the sequence should sequence should be alternating. That means this is greater than this is smaller than both element. This is greater than both elements like this.

[00:51:05]And similarly vice versa. Okay, cool.

[00:51:08]That means if if one element is greater than both is the adjacent element, it's adjacent element should be smaller than both s element. Right? So that means it should be here we got a condition. It should be alternating like 1 3 2 3 2 right? This is greater greater greater greater greater right.

[00:51:32]This is greater then this is smaller than both. This is greater than both.

[00:51:35]This is smaller than both. Otherwise 3 1 3 1 3. Then this is smaller than both.

[00:51:41]Right? Like this. These are alternating strings. We need to find these. And we are given one more condition which is for every adjacent pair the sequence I minus sequence I magnitude should be less than equal to one. That is one more condition. Difference of adjacent elements should be less than equal to M.

[00:52:00]uh magnitude of difference of adjacent elements should be less than equal to cool.

[00:52:06]Then what's the thing we need to find?

[00:52:08]We need to find the maximum possible element that can appear in any valid sequence. Cool. That means we don't need to find the sequence. We just need to find maximum possible element.

[00:52:24]Cool. Cool. Let's find it. Let's find it. Let's also see the constraints. Oh, N and S are 10^ 9 and M is 10^ 5.

[00:52:35]The constraints are N and S are less than 10^ 9 and M is less than 10^ 5. N means the vector length is 10^ 9. That means we cannot make the array, right?

[00:52:47]10 to 9 will give a T. Uh we cannot cover it in 1 second or whatever time constraint. Standard time. Yeah. Now S is the starting element. It's also 10^ 9. Then now M is 10^ 5. Okay, using now I have to tell what is the maximum possible element we can get. Okay, let's see it using some example.

[00:53:08]What examples we have n= 4, s= 3 and m= 5. This example is actually very you know revealing because this tell us that n= 4 s = 3 m = 5 and what could be the maximum possible number number we can get. Let's understand it using some other example to get more gist of it. Let's say n= 2 and m s= 3 and m= 2. Right? That means we have two inteious and the first integer would be s right now second as we need as maximum as possible number from all the array we want it alternating right if it's alternating that means either this would be the greatest element and this would be small either this would be vice versa as we know that this is already fixed and we know that the difference between these two elements s and let this element be b s minus B the module is less than equal to M right we this is also a condition first is alternating second is we have to follow this condition cool so I would want this to be greater the second element right because we I want as max as possible so if I do this s here is three the first element is three second how greater can I pick it I can pick it s plus m right because I have to maintain this right so s minus b is less than equal to m so I want uh let's say B is greater here right so if B is greater this would be B minus S less than equal to one so I want B to be as maximum as possible so B could be less than equal to M plus S so maximum this so yeah this otherwise you can just you know think by intuition if I can just add plus M here right because we don't want their difference to be greater than m so yeah I added this and this would be our answer which is 3 + 2 = Cool, cool, cool, cool. Here we got two observations.

[00:55:14]Mark S as lowest because if you mark S as lowest, S dash would be greatest.

[00:55:21]Again there will be lowest and here S double dash. Let's say this is double dash. This again would be greatest. So every time you can see that it is increasing, right? This decrease this would be this can be greater. Right?

[00:55:36]We will study about it. So this is the first that s make it as uh assume this is the lowest element right now the second thing we could do here is let's understand from this question now n is equal to four 1 2 3 4 s is first element three now I want second element as I'm assuming this is lowest then this is greater so this should be four towards some range as I want this as as great as possible this would be s plus 5 + s is equal to 8. So it is 4 to 8. I can take any element. I'll obviously take the largest. This would become 8.

[00:56:16]Now I want this as smallest. So what element can I make this? Because at my last what I want maximum to be largest.

[00:56:27]To make the maximum largest I would put it seven. Why seven? Because again when we when we are adding when we will add plus m here plus m here so I can get as maximum possible uh element right. So 7 + 5 is equal to 12 and this is as greater as possible if I placed it any element I can place it from this is eight right so I can make it eight as m is equal to five so I can also make it as small as three. If I made it three then again if we did plus m I would get got eight but I as I need as large as possible I can make add m again what's the pattern here observe the pattern here in 3 8 7 12 we got our answer right we can also cross verify 12 is 12 is our output now what can we do here uh we basically can the observation pattern here is First we add plus m right to make it as less as possible. Whenever we are decreasing we will do minus one right and whenever we are increasing we will do + m again right so observe this if let's say we had two more chances n was equal to 6 first let's see n is equal to 5 but n is equal to 5 this would be our largest element so this as we know this would be smaller so this would be 11 so this doesn't matter when n is equal to 5 we will search what would be the fourth element could be because this would be a greater element Right? Because we are assuming first is the smallest smaller one. Right? So we we would always want n / 2 into 2. This will give us whatever even number we have. Otherwise n minus n% 2. We would always care about this element. Right? This is our first observation. Our second observation could be the for first element we did + one. For here we got 11. Again we can do + 5 and we could get 16. Right? So here we did minus one. Here we did plus m.

[00:58:34]Then after m for every update what we are doing here min -1 + m what we are doing here min -1 plus m -1 + we would only add m minus one can I say this on the first one if I divide it on boxes of two on boxes of two as I just told if there is we can always divide it by boxes of two if there is odd we will not consider it because there is no point right that that large number after it we will take 15 this is less less right because we assume the first number to be less as well. So all numbered would be the lesser numbers. So yeah we observe if I take in boxes of two I know that for every box the first box we will add plus one and for every consecutive box we will add m minus one. Right? This is our main intuition. For first box we add plus m and for others we do m minus one.

[00:59:32]And how many boxes we have? Boxes number of boxes is equal to n / 2. Can I say this? Yeah. Because odd number does not matter anyways. So we can do the floor division here. Right? So I can say is the final answer would be s + m of the first box plus number of boxes minus one. We are leaving the first box into m minus one. This would be our final answer.

[01:00:07]Right? For here our first element was three and first we did + 5 and for number of boxes let's say we had three boxes 3 minus one into m is again 5 minus uh m minus one right min - one. So this is 4 into 2 + 5 + 3 8. This becomes 16.

[01:00:31]Is 16 our answer? I took this right.

[01:00:35]Yeah, 16 is the answer.

[01:00:40]Let's also see the code.

[01:00:46]And the code is pretty simple. This operation is actually number of boxes.

[01:00:52]boxes, right? This is n divided by two.

[01:00:55]If boxes are zero, then there is only one element, right? So, we are going to return s as well. Otherwise, s starting element plus number of boxes minus one, m minus one plus m. This is for this first box and this is for the later boxes. And then we are going to return what would be the time complexity here.

[01:01:19]We didn't do any iterations. We didn't do anything right. So the time complexity here would be of one as well as the space complexity because we didn't do any of like we just did normal math and saved it in the variables.

[01:01:44]Now let's discuss the problem C which is I guess the most demanded problem out of all the most demanding problem and then we'll move.

[01:02:10]Hello.

[01:02:14]Let's go for a chat.

[01:02:18]Please tell me, can anyone tell in the audience if my mic is perfectly fine and audible and um it's good to go and also I'm reading comments. If you use integer division, we won't get odd and even case for C, you are calculating it, right?

[01:02:39]C I think was an easier problem. It's sort of okay. Cool.

[01:02:45]Cool. Cool. Cool. Let's start with the problem. C now.

[01:03:06]uh your B solution is so easy to understand. Took me 1 hour in contest to come up with something like that. Yeah, thanks to let's talk about DSA now. We can talk about it later.

[01:03:28]In question three, can you solve it using fragmentaryary? Question three is simp simpler. Dude, what are you doing?

[01:03:34]Uh I'll I'll explain it with the easiest code I have right believe me C is very easier easier than you think it's like normal math or normal observation you sound like Dan I'm not sure who is dwan then like whichan are you talking about can you specify And yeah, let's start with the problem C. Now let's let's try solving it.

[01:04:17]Why you like solving it with peg? I'm not sure like let's let's see now. So minimum adjacent swap to the partition array. You are given an integer nums and two inteious A and B such that A is less than B.

[01:04:31]Cool.

[01:04:33]Problem C. We are given an integer array. What's the integer array name?

[01:04:37]Nums.

[01:04:44]Uh, and we are given two inteious. These are integers such that a is less than b.

[01:04:49]So an array is called good if it can be split into three continuous part in this order. Every element in the first part is less than a. Every element in second part is range A to B inclusive and every element in third part is B. Any of these three parts may be empty. Cool.

[01:05:10]So we are given definition of a good array. A good array is array such that the first it has three parts. The first part all elements are less than a. These a and b we are using it here. These elements are from a to b inclusive that that means it can be a and b.

[01:05:29]and this uh can are greater than C. Any part can be empty. That means this can be empty. But yeah, if the they exist there will be in this order. Cool. Cool.

[01:05:42]And then we are told that in any existent swap you may swap two neighboring elements. This is one operation, right? And then we have we are told that we need to find minimum number of swaps to make nums good. And since the answer may be large, return it in modulo. Okay, cool. Great. We are given one operation or one swap which is that we can do one adjacent swap. That means in an array, let's say this is an array, we can swap these two elements or any two adjacent elements. This will cost us one operation. And finally we need to find minimum operation two minimum operation to make array good.

[01:06:26]Yeah, that's that's good to know. This is the question that we are given an integer array nums two integers that a is less than b. These are basically ranges, right? And then we are told as a good array is something that first part is less than a second part is a to b inclusive third part is greater than c.

[01:06:46]Then we are told that we can do one operation which is we can swap adjacent elements and make operations minimum operations to make the record. Okay, cool. Let's see the constraints now.

[01:06:56]The length of array is less than equal to 10^ 5. Each element a and b all are 10^ 9 less than 10 greater than one.

[01:07:06]This integer array size is less than equal to 10^ 5. And all these elements as well as all the elements in the array they are all less than equal to 10^ 9.

[01:07:19]Right? 10^ 5 that means we cannot do loop twice or something like that.

[01:07:24]Right?

[01:07:25]Now let's see with some example.

[01:07:29]Let's use the example here. We have some good example. This is I think good. 9753 and 48.

[01:07:38]97 53 A = 4. B is equal to 8. Can I write it like a range? This is a range that we are given. Now what I need to basically make it into three partitions where all the elements are less than a or less than four where all the elements can be this in range 4a 8 there could be from four to 8. So here all elements will be greater than all elements less than uh a r only we have this element right. So yeah only one those who are in this range there are two elements 7 and five 5 7 or 7 five doesn't matter right and then we have to make this segment uh such that all the elements greater than eight which is one 9 right this is a final array but we don't need it we need the swaps to make it cool how can we find the swaps 9 7 53 3. This is our array and our range is 4 to 8.

[01:08:42]A = 4, b= 8.

[01:08:52]Let's see now how can we solve it. We know that the first is less than a. Then we have the middle elements and then we have greater than b.

[01:09:02]So what how can we solve? We know the final array would look like some 3 7 five or 9 or something like that right so I know that like if we can swap it let's swap these two elements this would become 9 7 3 five and then I can swap these two element I want to make this three the first element right let's make it first so this becomes 3 75 9 then these two elements this become 3 975 cool this is this is at its position now this nine should be at last Let's make it. Let's wrap them. Okay. 37 95. Let's wrap them.

[01:09:40]3759.

[01:09:42]Cool. Is this array good? Yeah, this is good to go. How many operations we did?

[01:09:46]This was our first operation. This is our second operation. This was our third operation. This was our fourth operation. Right. So, we did four operations.

[01:09:57]Oh, sorry, five operations.

[01:10:00]Uh we swap this, we swap this, we swap this. Oh, this we go went above, right?

[01:10:06]Yes. Sorry. Five options.

[01:10:09]Five is our answer. Cool. Now, how can I find it from this example? Can you notice something? What we did? We had 9 7 5 3. We know we need to make three different uh three different segments, right?

[01:10:28]Just notice something. This three has to be in the first segment. Let's say I had two two. These both should be in the first segment. This three has to swap among all the elements and then get here. Right or wrong? Right? This has to be the first element. This can be second element or this can be first element.

[01:10:47]But let's we know that preserving order works right. What about if I first move this three towards its position which is the first element then I can move this towards it the towards the second element right how can I move this I can just you know swap swap swap and swap let's say 9 753 and 2 I can just swap these two elements this become 35 79 I can swap again this becomes 3759 I can swap again this becomes 3 975 and 2 right so here I just swapped swept swept and became the first element which I want to be in the first segment. I want all the numbers less than four like three 2 or even one. So I would want that this three should be the first element. Why? Because this in order of elements that are less than four this is the first element. That means to move this three from here to the first element there are two parts of it. First you should believe that this should be the first element. Why? Why not this? I know the f why this first I need all the elements less than four. These two are less than four. Right? But why specifically three should be the first element? Because this becomes this occurs first. Right? Any point of time if this becomes first that means these two have been swapped. Right? These two must be swapped so the two can become before it. Right? And we don't want it.

[01:12:13]That's absolutely unnecessary. We don't want the array to be in a sorted order.

[01:12:18]We just want them in segments, right? So this should be our first element. That mean this has to jump over all these elements. Cool. This become the first.

[01:12:27]Now what about this two? This two has to be second after we reach here. Now what's the array? We have 3 9752.

[01:12:38]Now for this array, doesn't this has to be in the second element? Yeah. Yeah, we have to again the same logic that as we need to be on the second element, we have to pass on all this. Yeah, we have to. So, how many operations are we going to make here? 1 2 3. The number of elements in between three operations and the array would look like 3 2 uh 9 75.

[01:13:03]Just notice something. We we got our first segment. We got the first segment.

[01:13:08]Now, we need we have two segments that we need to make. First is the middle segment and we have the rest of segment.

[01:13:15]I know that if I make any of these segment the other segment would easily be made. If I make this segment that mean these two are here then only this segment left right and only those elements will be left. Yeah, cool. Then I just have to make any ele any segment.

[01:13:29]Now the logic is same for this array or any array. Let's say you iterated once and found this. Now you can iterate again and you just have to find the another segment. For example, let's say we are finding this segment. Now, this nine has to be the last element. Has to be last.

[01:13:49]That means I have to pass over these two elements. Let's say we also have 10 here. That means this 10 has to also pass these two elements. Right? First I will pass nine. How many elements we have in between? Two. So, we got two operations. And for this 10, two operations. We got plus four operations.

[01:14:04]But we don't have 10. So, we have plus two. We got plus two operations here.

[01:14:10]Right. So we for how many total operations to make three we got one two and three we did three operations for three we did three operations for two and for 9 we did two operations. So total 3 + 2 5 + 2 7 operations. This would be a final answer. I hope you got the gist.

[01:14:34]I did question three using count inversion. you yeah you can do it but that's too complex right I that's not complex but for beginners I would suggest let's go with the first principle which is like sorting and iterating I hope you got the solution right so I did two loops here the first loop is to make the first segment right so whenever I reach it to let's say again we have a= 4 and b equal to 8 27 39 27 379 I know that this is Perfect.

[01:15:06]Good to go. So this should be in index zero. This is at currently index zero.

[01:15:11]This should be at index z. This is at its place. Right? So here I'm doing answer plus equal to current position minus position it has to be in.

[01:15:27]If I do mod I can do it on the both side. So again after doing this the position we have to be in is zero. is one position we have to be in is now one. Initially it was zero. Now it become one and current position is seven. Do we need to turn seven? No. Now we are at three. Is three less than four? Yes. If it's yes then we have to again pass it. And how many elements we have to current position minus position it has to be in. So the position it has to be in is one and the current position is equal to two. So we got one. These are basically the middle elements.

[01:16:01]And we know that the middle elements will never be first segment elements because if it's a first segment element type two it is already in its place right we're always finding the last element last occurrence of uh the first segment element and similarly after sorting it for the first time we will do it for the last segment. Is it crystal clear friends peeps? Is it crystal clear?

[01:16:35]Let's also see the code. I hope this gives you right. Current position minus position it has to be in. Right. First we will do for first segment and then we'll do for last segment.

[01:16:48]Let's see the code.

[01:16:52]There are a couple of approaches X or don't like this is for as we last we need to do modulo 10^ 9 + 7 right we need to return in it I take long long because you know the total number of segment or total number of operation would be always less than 10^ 15 16 or whatever long long is like larger right 10^ 18 19 or something on that range so yeah first we are what we are doing this P is our position we need to be in right this P is position we need to be in this is for first segment right once I do the first segment how I'm implementing for last segment now this is for last segment that is why P is equal to last segment because after doing last segment the rest of elements will already be in range right doesn't matter what segment you do anyways this ex tells us already place first elements as we know that we cannot do literal swaps right doing swaps like this like we did for three swapping one by one by one will take a lot of operation and time right so I'm making this ex will tell us the elements which are already in place and are in the beginning for example let's say we have array like 3 9 sorry 9 3 7 right we know So that after first operation this three would go here and the array would look like this. But we are not making the operation. So the array is again like this. Now if I have to do it for last segment the current position when it is this and b is equal to 8 and a is again four. We know that this should be look like this should look like this right? But it's not. And now the formula changes. Answer plus equal to current position which is this I =0 minus position we have to be in position we have to be in which is this position and minus this ex here the variable is ex or elements already in placed elements already placed as we are iterating from last to first let's say this is only this element comes in between that means ex would be equal to one right so this is I = two here the position we have to be in so this becomes 2 - 0 - 1 = 1 which is exactly one swap after this we will take one swap and we will reach right this is the logic behind x already place element are placed in first segment Right. And this is our updated formula.

[01:19:48]So no first segment elements are counted in swaps dash position or operations as they are already in their place in the starting finally answer percent and then we are returning it Again, this question is by far the best because the last question is nothing but a variation of a standard question.

[01:20:27]Minimum. Let's wrap it fast because there would be another PCB. What's the time complexity here?

[01:20:34]As you might have already guessed, time complexity would be of n or of 2 * n because we are iterating twice and space complexity would be of n because we are storing the array.

[01:20:52]Now let's jump towards the last question. Minimum cost to convert the string three. You are given two strings source and this target. You are given 2D string rules where rules I is pattern I replacement I and an integer cost where cost I is the base cost of applying rules I both arrays have same length.

[01:21:10]Additionally pattern I and replacement I have same length. You may apply any number of rules any number of times just one for each rule this is applicable.

[01:21:20]Choose a length tells us that range of L to L + pattern. Length whatever pattern you're choosing minus one exist in the current string and none of these position have been used in a previous application. For each index J the character J must be either equal to the current character or L + J should be equal to this. Replace these character with the range. Let me actually explain it as right. So in this D we are given two strings. The first string is T S sorry.

[01:21:56]Uh here we go. The first string is source but the another one is target.

[01:22:02]This is a source string. This is a target that we want to achieve. These both are strings.

[01:22:08]And we are also given this rules vector. In this vector we will have two strings.

[01:22:18]This is a vector. So it is a vector of vector of strings. So this will be like this. At every place we will have a pattern and we will have a replacement pattern replacement and also we have a cost right which is the base which is uh an area of integer which is the base cost of this operation.

[01:22:47]What is the operation? Operation is simple uh operation or rule whatever you call it right these are rules so the rule is something like for a pattern you are reading it right so replace first we need range of position from L to L pattern I minus length minus one to apply any rule I to apply any rule I right at first we need to ex see that these position exist Right? Then we need to check for each character J in this pattern. Right? It should be equal to L + J. Right? Or like star. What does this mean? This mean that we have this operation.

[01:23:33]This operation is something like let's say this is a string.

[01:23:38]To apply an operation here the pattern and replacement this string let's say this is a star. This is a string right?

[01:23:45]We can have stars here. And let's say this is B star BD. We cannot have stars in replacement. But basically intuitively tells us that for this pattern in the string we can convert it into this string and the cost will be cost plus number of stars we have in the base string.

[01:24:07]Right? So the total cost would be cost plus number of stars we have in the base string. And uh what we are told is basically for this string. Right. We can how can we apply this operation? The pattern a star exists here. Yeah, this is what they here told telling us that the pattern should match either the character should be same, this character should be same otherwise there should be star here. Right? That's what it's telling and we are telling that we can replace this range by replacement. That is for this A and B after performing this operation we can convert it to B and D.

[01:24:47]And the cost of this application would be cost I the base cost plus number of characters star which is cost I plus number of star characters which is here one number of stars. This would be the cost of this operation. After this this will become df. The string is changed from this to this. Right? And what we are told like what every DP solves right the minimum total cost to transform source to target if it's impossible return minus we this is our source this is a let's say this was our target so what we did here we use a star here and we converted into BD right that means for every range we will have this option right now let's see the constraints The constraint here is basically the source length is less than equal to 10^ 5. Number of rules is less than equal to 200 I guess. Yeah 200 and length of a rule is less than equal to 20. These are the constraints. So you can see that yeah we have uh number we can like the first intuition that should come into your mind is basically now what we need to do is find the minimum cost for it.

[01:26:19]And how can we find that? Let's see using some example. Let's say we have a b c d. This is our source. Now target is t e c d. And our rules array look like A star comma D and the next we have let's say A B and this is also D E and next we have AF and then OP the length of both will be same always these are the rules and the cost array let's say the cost here is five the cost here is 10 and then cost here is 50 what we need to do is convert this string into this. How can we convert it?

[01:27:06]We know that these rules are basically replacement rules. I can find this in the array and I can replace with it. Our very first intuition is we have this A and B. I can use this rule and I can convert as because they match. Right?

[01:27:18]This is a star. This is the rule. This is the pattern we need to match.

[01:27:24]This matches with this. So yeah, let's uh replace it. Replace AB with D. And the cost of this approach would be cost one would be the base cost which is five plus number of stars. We have one star one which is six. Cool. We also have another approach. We also have AB here.

[01:27:43]So we I can use this rule. AB will match with AB and I can replace this AB with DE. Right? So this would become DE CD because AB is replaced with D and these both are again equal. the cost of it would be base price 10 plus number of asterics which is zero we got final 10 and now we need now again we don't have any other option right af does not exist here so yeah I cannot apply it anyways I can just apply these two and also there I there is one thing that if I am applying applied to this segment I cannot again apply from start from B or anywhere I have to start from C right so now what is the minimum cost minimum cost is this Anyone who like knows DP DP is the prerequisite for this problem could understand this. I can solve it using a normal DP right. Why? Because I can say DPI is minimum cost to make first I elements of source and target equal.

[01:28:53]Can I say this? Yeah, sure you can say this. What would be the transition here?

[01:28:57]Let's understand it. Let's say source is A, B, C, D. And let's say we have F here and target here is F A B and then we have E F uh no AB D E and E F. This problem will explain everything. And let's say the rules we have AB we can convert it into uh DE and another rule we have that CD C star we can convert that into EF right these two rules we have and the cost array is something like five and 10 and what can we do here Let's add one more rule actually a star B they are these three rules now the cost would is something like 5 10 5 right so what can we do here DPI tells us uh the minimum cost to make both elements both I elements equal right so we'll start from zero element. Are they both equal? Yeah, they are equal. So DPI is would be equal to if uh SI let's equal to equal to TI DPI would be equal to DPI minus one I minus one cool minimum of DPI or DPI minus one right there could be minimum DPI otherwise otherwise what let's say we are here here A and D are not equal not equal anyways if it's not equal or equal we will going to perform on the rules. The rule says us that we can convert this AB to C star C C E uh DE sorry this rule right otherwise we can convert A star into D I can apply any of these two rules right so I can check all rules all rules and see what applies see what we can apply we can apply Right. So there are two things we are doing. First check how are we going to check the source I to whatever size we have right this should be equal to equal to whatever pattern we have right for any rule. And also one more thing after this rule this would be converted into target right. Yeah, this entire can be converted into target. This target should also be equal to whatever target size we have. Right. Exactly. Right.

[01:31:54]Let's say I have one more rule which is AB to let's say OM. This AB matches here. Should I apply? No. Because OM does not match here. Right? So I have to match both the pattern as well as target.

[01:32:10]First I will check this. This means yes, we can apply. We can apply. How are we going to apply it? The DP transition state would look something like DP I + size minus one. Why size min? This tell us the last element we are checking, right? Equal to DP obviously minimum of DPI + I minus one. There could be already some value already there, right?

[01:32:39]Comma. Now the main value value comes DP I minus one whatever minimum cost to make the DP first I minus one characters equal plus cost J whatever the rule we are applying plus number of estrix in uh pattern right this this is the entire DP state that we have to If first we check if both are equal.

[01:33:11]Yeah, we can apply now this. So here what will happen? Here DP0 would become zero. Right? Because both are already equal. DPI minus 1 does not exist for the first element. Now F A B C D right.

[01:33:27]F A B C D F D E uh F. Right. Right. Right.

[01:33:38]Now for this I know that there exists two rules. One is a star and a these two I can apply. The cost of one is six and the cost because this is 5 + 1. You can check from here. The cost of applying this a star rule is five plus number of extract one six and the cost of AB is five.

[01:33:59]Cost of AB is five. Also I both converts into DE.

[01:34:04]So I can apply these two rules right. So DP I plus size minus 1 is our formula right size is equal to 2 size is the size of rule plus I is here 1 this is minus one so this becomes 2 + 1 3 - 1 2 DP2 is equal to DP I - 1 I -1 plus cost plus ax or total cost total cost right DPI minus 1 is equal to 0 1 DP0 right and total cost is here for this rule it would be six that's why and for this rule it could be five so that's why we are doing minimum of DP whatever this value is so first I'll do this and do this so DP 2 finally would become equal to 5 now again at DP P3 sorry at I = 3 I will get option of doing this uh the rule CD to EF rule the cost of it is 10 I as far as I remember yeah the cost is here is 10 this C star to EF 10 + 1 10 + 1 this would be total cost Right.

[01:35:37]And this would become uh third DP four right four or five four uh DP4 and some value DP4 is actually DPN minus one because we have five characters and this finally we are going to return this for uh 0 to n minus one characters. What is the total minimum cost?

[01:36:09]Let's see the formula.

[01:36:13]Right? Again, same thing. First uh infinity setting the value of infinity.

[01:36:18]N is total size and this is the DP.

[01:36:23]Iterating all rules, right? This FI is the final index, right? Here I'm checking if the index goes outside right this should not go outside this means I cannot apply rule for example uh when we are checking for this uh when we are checking for this character for i equal to four basically last when we are checking for this I cannot check any rule because these sizes are two right and this here is size is one only one character is left basically they're match that means again I'm checking if source should be equal to either arc or the source or the rules and the target should be equal to the replacement we are going to have if it also I'm calculating number of aster total cost is cost plus number of asterics and dp fi is minimum of dpfi plus temporary and if both uh characters are equal dpi is equal to dpi minus one if i minus one exists this is what I'm checking here and Yeah. DPN minus one equal to if it's greater than infinity that means we cannot make it we are going to return minus one otherwise n minus one. How what's the time complexity here?

[01:37:45]Time complexity basically we are multiplying two three things here.

[01:37:55]Where is the question number div?

[01:37:58]This is here we are multiplying this uh understand it in forms of DP DPI as we are iterating from zero to n minus one elements we are doing n into we are every time we are checking for all the rules and uh for all the rules right so to iterate each and every rule this is costing us 2 into 20 into two actually because the rule There is star pattern as well as target.

[01:38:31]But this is we have this we can actually know because we are iterating once. This is 200 into 20 and it's 10^ 5 10^ 5. KN source length is 10 to power what is it? 10^ 3. Right.

[01:38:52]5 5,000. Sorry. Sorry. Sorry. Yeah. 10^ 3. This is 5k.

[01:38:58]5,000 into 200 into 20 5 200 to 4 into 20 into 10^ 6.

[01:39:07]So 2 into 10^ 7 iterations which sometimes work in deep code and sometimes it does not.

[01:39:14]But yeah, usually it works. Yeah, it's it works. And yeah, that's all for today's VCD.

[01:39:24]I hope you folks like the postcontest discussion.

[01:39:29]At last I'll tell to please like and subscribe for good rating for positive delta in rating.

[01:39:49]That's all from my side. Let's actually wrap it up. If you folks have any question, you can always ping it out on the comments or reach out to us. Do subscribe your T limits channel. Do follow our Instagram. Do follow our LinkedIn. Do ping us, comment us, do repost us, do comment on our LinkedIn video and whatever you like. See you folks. Bye. Have a nice night.