String Compression II - Leetcode 1531 - Python
Vložit
- čas přidán 27. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑💼 LinkedIn: / navdeep-singh-3aaa14161
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/string-...
0:00 - Read the problem
0:12 - Drawing Explanation
10:19 - Coding Explanation
leetcode 1531
#neetcode #leetcode #python
They saved the best for the last😂. Thank you for explaining so well, it was a really tough problem.
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 !!!
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?
Thanks for your persistence do this video series!
Thank you for explaining the solution. you are really brilliant and extraordinary.
great explaination man!
keep going bro!
thank you for such an easy explanation :)
Today's daily leetcode challenge was difficult.
Need to look for video 😂
phenomenal work, you gained a sub and a follower 💯
Thanks bro ! Good explanation Even gpt couldn't solve this problem ...
Thank you, it saved me
Thank you so much
Is using func_tools cache to save sometime a bad idea in an interview? (for memoization)
This is a very difficult question. Thank you for making this video. It makes a little bit more sense now. lol
Can’t love your videos more😂
questions like this is almost impossible to solve in a real interview
What an explanation...
So amazing
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.
Off topic but the discord link in the description Is not working (i wanted to join the server)
thank you
best explanation for this question. I was so traumatized until seeing this. Thanks for sharing
like what if we condensed the string first and later doing the computations
How to convert it to 2-dp because some solve it in....?
God tier explanation but TypeScript compiler says it TLE when using Map()😂😂😂
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.
How will I be able to develop intuition like that?
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.
How to do the opposite?
man fuck this problem, took me a bloody day to solve
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.
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?
Saviour !
bruhh, in the morning doing the problem, guy has already got the solution ready, hats off
I see hard and I quit
I see medium and I watch
I see easy and I solve
I relate so hard.
clutchhh
I wrote it in Java version but 122/144 got TLE... Why
How the heck will I come up with this solution on spot in an interview, these problems are real tough
I dont understand why he did ... note updated the deleted character? can somebody explain?
Don’t understand your question
If I get this on an interview. I'm just going to walk out
class Solution:
def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
@cache
def dfs(i, k, prev, prev_count):
if k
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
This aproach is giving runtime error due to stack overflow.
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.
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
Why does he sounds like Bane (Batman) giving savage dialouges?
The same solution in Python beat 79% of users for me
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.
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
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
This solution had beaten 100% of users in runtime and memory, LEETCODE is broken
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