Thank you for the explanation! I was able to solve this problem using a condition 'window contains the min number of t characters' however I was using a set and two frequency maps so the solution was slow. It is nice to learn about a better & faster way to solve these problems with just one frequency map :)
One thing I don't get is why minLen is set to Max_Value. For line 33 isn't it usually always going to be true? I don't understand setting curWindow to minLen also. Could you explain? Thank you!!
ok, I stepped into the code and I think you set an artificial large number to avoid chances of overlap. What's important is the while condition that matches the condition and assigning of minLen to a min window length to get the operation started. Thank you!!
The way I think about it is, say you're looking for the cheapest car in a list of cars. So you set a minCar value to like 1,000,000 and then as you check cars, if you find one less than that, you update the minCar value to that value (say 400,000). If you find something less than THAT, update again, and then at the end whatever minCar is, that's the cheapest one. But what if every car on the list is actually greater than 1,000,000? Then minCar never updates, and you "think" the cheapest car is 1,000,000 since the value was never updated. That's why you set the minCar value as high as possible from the beginning. This way the first time you test a car, it will ALWAYS be the cheapest, so the minCar actually updates.
at the point u get to the shrink logic your R pointer is ahead already, so map[arr[right]]--; will make sure the character will be -1 before ++arr[leftChar]
Thank you for the explanation! I was able to solve this problem using a condition 'window contains the min number of t characters' however I was using a set and two frequency maps so the solution was slow. It is nice to learn about a better & faster way to solve these problems with just one frequency map :)
thank you for your explanation!
You are welcome!
great Job!! Thank you.
Thank you too!
Thank you so much, bro!
Please do mention Time and Space complexity of the code in the description
I believe the time is O(n) and time complexity is O(n) as well
Amazing trick!
Thank You!
You're welcome!
One thing I don't get is why minLen is set to Max_Value. For line 33 isn't it usually always going to be true? I don't understand setting curWindow to minLen also. Could you explain? Thank you!!
ok, I stepped into the code and I think you set an artificial large number to avoid chances of overlap. What's important is the while condition that matches the condition and assigning of minLen to a min window length to get the operation started. Thank you!!
The way I think about it is, say you're looking for the cheapest car in a list of cars. So you set a minCar value to like 1,000,000 and then as you check cars, if you find one less than that, you update the minCar value to that value (say 400,000). If you find something less than THAT, update again, and then at the end whatever minCar is, that's the cheapest one.
But what if every car on the list is actually greater than 1,000,000? Then minCar never updates, and you "think" the cheapest car is 1,000,000 since the value was never updated.
That's why you set the minCar value as high as possible from the beginning. This way the first time you test a car, it will ALWAYS be the cheapest, so the minCar actually updates.
Wouldn't ++arr[leftChar] > 0 hold true for every character?
at the point u get to the shrink logic your R pointer is ahead already, so map[arr[right]]--; will make sure the character will be -1 before ++arr[leftChar]
Store freq if t in 1 map and change it acc to main string and finally give output
It's very weird that your code runs at 7ms and mine is around 125ms. Both are exactly the same code. Magic?
It's happened to me a lot of times