Well explanation that saved my life!!! I am able to apply what you have taught in the video and solve today's leetcode question. This is encouraging for me !!!
No way you actually make difficult problems with such clarity! I visit this channel every day, no matter how easy/hard the daily question is just to see your approach.
It may be because you are using map, which is ordered and slow. Use unordered_map instead. You need to define a hash function since you are using a vector as key. struct vector_hash { size_t operator()(const vector& v) const { hash hasher; size_t seed = 0; for (int i : v) { seed ^= hasher(i) + 0x9e3779b9 + (seed2); } return seed; } }; unordered_map dp;
@@v-free hey can u tell how i can learn to make custom comparator and custom hashfunction i have tried it from some of the internet tutorials (mostly written ones) please lmk know if u have some resource or tips for me to help me learn those thank u
Shouldn't we also consider the case of deleting s[i] when it is the same as the prev character? Like if we have the string "aaaaaaaaaaaaaaaaaaaaaaaaa..." (25 times a) and the k is 20, then we need to delete so that it is not a25, but a5 instead.
Heyy Bro, your solution and way of explanation was amazing but still I am trying to understand this and how can I come up with this level of intuition to solve the problem. I was able to come up until greedy approach and got 74 passed.
Couldn't we just get the encoded string first and try to shrink it with a recursive function? Or will the addition of computing the encoded string give a TLE? EDIT: Nevermind this won't work, I thought run-length encoding would transform a string like "aabbaa" into "a4b2", but the encoding is actually "a2b2a2". If k = 2 in this case, the minimum length string would be "a4" with length 2. Indeed a hard problem.
Lol I was so happy in the beginning thought “oh! That’s not HRAD!” Codes up this exact solution in like 10 min then also ran into this test case. Banged my head for the rest 30 min then gave up, lol. But after watching this solution does make me believe the condensed list will still work if we keep track of the previous character, which I did not implement this resulting in the failed case you gave.
didn't understand why it fail in greedy approach here? even when we consider our string as s = ''aaaaaaaaabaaaaaaaaac' and k = 2 s compressed = a9ba9c so deleting minimum window freq element here ''b' & 'c' implie "a18" with lenght 3. can someone explain this?
We add cache when we know that for a given set of input the output is same and their should also be overlapping sub-problems. In backtracking cache is of no use as mostly the sub problems are independent and doesn't occur more than once eg: Sudoku, but in DP same sub-problems occur eg: Fibonacci(try to draw tree of recursive call to better visualize).
Same solution Runtime 1552 ms Beats 91.00% of users with Python3 Memory 39.88 MB Beats 40.00% of users with Python3 No !dea why leetcode does this sometimes
Because when we encounter 1 -> 2 (a -> a2) 9 -> 10(a9 -> a10) 99 -> 100(a99 -> a100) all of these cases will result in answer to be plus by 1 and the rest of the case don't need to do this because the length remain the same like 3 -> 4(a3 ->a4)
I mean this is cute and everything, but what the hell is the use of solving these. They have no practical application whatsoever 😂 AKA utter waste of time
They saved the best for the last😂. Thank you for explaining so well, it was a really tough problem.
changing one of the base cases from i == len(s) to len(s) - i == k helped my runtime dramatically
it removed my TLE bro thanks
Thanks bro, this help TLE too!
@@khushmeetchugh8669 C++ magic
This removed my TLE for Java, thank you
can you please explain the logic behind this base case change?
Well explanation that saved my life!!!
I am able to apply what you have taught in the video and solve today's leetcode question. This is encouraging for me !!!
Today's daily leetcode challenge was difficult.
Need to look for video 😂
questions like this is almost impossible to solve in a real interview
No way you actually make difficult problems with such clarity! I visit this channel every day, no matter how easy/hard the daily question is just to see your approach.
This is a very difficult question. Thank you for making this video. It makes a little bit more sense now. lol
Thank you for explaining the solution. you are really brilliant and extraordinary.
If I get this on an interview. I'm just going to walk out
best explanation for this question. I was so traumatized until seeing this. Thanks for sharing
Thanks bro ! Good explanation Even gpt couldn't solve this problem ...
class Solution {
mapdp;
int solve(string &s, int k, int i, char prev, int prevCnt){
if(k
It may be because you are using map, which is ordered and slow. Use unordered_map instead. You need to define a hash function since you are using a vector as key.
struct vector_hash {
size_t operator()(const vector& v) const {
hash hasher;
size_t seed = 0;
for (int i : v) {
seed ^= hasher(i) + 0x9e3779b9 + (seed2);
}
return seed;
}
};
unordered_map dp;
@@v-free hey can u tell how i can learn to make custom comparator and custom hashfunction i have tried it from some of the internet tutorials (mostly written ones) please lmk know if u have some resource or tips for me to help me learn those
thank u
Thanks for your persistence do this video series!
class Solution:
def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
@cache
def dfs(i, k, prev, prev_count):
if k
thank you for such an easy explanation :)
Thank you, it saved me
Thank you so much
thank you
great explaination man!
keep going bro!
What an explanation...
So amazing
The same solution in Python beat 79% of users for me
man fuck this problem, took me a bloody day to solve
Can’t love your videos more😂
I see hard and I quit
I see medium and I watch
I see easy and I solve
I relate so hard.
God tier explanation but TypeScript compiler says it TLE when using Map()😂😂😂
bruhh, in the morning doing the problem, guy has already got the solution ready, hats off
Shouldn't we also consider the case of deleting s[i] when it is the same as the prev character?
Like if we have the string "aaaaaaaaaaaaaaaaaaaaaaaaa..." (25 times a) and the k is 20, then we need to delete so that it is not a25, but a5 instead.
Heyy Bro, your solution and way of explanation was amazing but still I am trying to understand this and how can I come up with this level of intuition to solve the problem. I was able to come up until greedy approach and got 74 passed.
like what if we condensed the string first and later doing the computations
How to do the opposite?
Off topic but the discord link in the description Is not working (i wanted to join the server)
How will I be able to develop intuition like that?
Saviour !
clutchhh
Couldn't we just get the encoded string first and try to shrink it with a recursive function? Or will the addition of computing the encoded string give a TLE?
EDIT: Nevermind this won't work, I thought run-length encoding would transform a string like "aabbaa" into "a4b2", but the encoding is actually "a2b2a2".
If k = 2 in this case, the minimum length string would be "a4" with length 2. Indeed a hard problem.
Lol I was so happy in the beginning thought “oh! That’s not HRAD!”
Codes up this exact solution in like 10 min then also ran into this test case.
Banged my head for the rest 30 min then gave up, lol.
But after watching this solution does make me believe the condensed list will still work if we keep track of the previous character, which I did not implement this resulting in the failed case you gave.
How the heck will I come up with this solution on spot in an interview, these problems are real tough
phenomenal work, you gained a sub and a follower 💯
didn't understand why it fail in greedy approach here?
even when we consider our string as s = ''aaaaaaaaabaaaaaaaaac' and k = 2
s compressed = a9ba9c
so deleting minimum window freq element here ''b' & 'c'
implie "a18" with lenght 3.
can someone explain this?
How to convert it to 2-dp because some solve it in....?
do we add cache evetime in question of DP or backtracking ? If not when do we add them ?
We add cache when we know that for a given set of input the output is same and their should also be overlapping sub-problems. In backtracking cache is of no use as mostly the sub problems are independent and doesn't occur more than once eg: Sudoku, but in DP same sub-problems occur eg: Fibonacci(try to draw tree of recursive call to better visualize).
To memoize the recursive solution, otherwise you are gonna get a TLE.
Is using func_tools cache to save sometime a bad idea in an interview? (for memoization)
I was allowed to use it, as long as you explain how it works...
Why does he sounds like Bane (Batman) giving savage dialouges?
Same solution
Runtime 1552 ms
Beats 91.00% of users with Python3
Memory 39.88 MB
Beats 40.00% of users with Python3
No !dea why leetcode does this sometimes
I wrote it in Java version but 122/144 got TLE... Why
This solution had beaten 100% of users in runtime and memory, LEETCODE is broken
This aproach is giving runtime error due to stack overflow.
I dont understand why he did ... note updated the deleted character? can somebody explain?
Don’t understand your question
The example2 is indicating that minheap does not work but I still waste time for that...
Nah. it will work for example 2. I tried it.. greedy passes 74 tc.
why is it so hard.....goddamn
This one is hard, isn’t it.
@@0ManPiano0 I'm having a hard problem everyday...at least one.....this one's painfully hard for me
Can someone please explain me about the increment part 14:04 to 16:00?
Because when we encounter
1 -> 2 (a -> a2)
9 -> 10(a9 -> a10)
99 -> 100(a99 -> a100)
all of these cases will result in answer to be plus by 1
and the rest of the case don't need to do this because the length remain the same like
3 -> 4(a3 ->a4)
your explanation helped me to understand that part.@@w702897028970289
I mean this is cute and everything, but what the hell is the use of solving these. They have no practical application whatsoever 😂 AKA utter waste of time