String Compression II - Leetcode 1531 - Python

[@MP-ny3ep]

They saved the best for the last😂. Thank you for explaining so well, it was a really tough problem.

[@Sinders]

changing one of the base cases from i == len(s) to len(s) - i == k helped my runtime dramatically

[@khushmeetchugh8669]

it removed my TLE bro thanks

[@gmasid]

Thanks bro, this help TLE too!

[@raghavbhatia5548]

@@khushmeetchugh8669 C++ magic

[@yang5843]

This removed my TLE for Java, thank you

[@karanshah2283]

can you please explain the logic behind this base case change?

[@Drdarker]

questions like this is almost impossible to solve in a real interview

[@bhavikransubhe7244]

Today's daily leetcode challenge was difficult. Need to look for video 😂

[@s20061002]

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 !!!

[@tony7948]

If I get this on an interview. I'm just going to walk out

[@ujjwalmaheshwari2327]

class Solution { mapdp; int solve(string &s, int k, int i, char prev, int prevCnt){ if(k

[@v-free]

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;

[@lokeshmehar3949]

@@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

[@urjeans2896]

best explanation for this question. I was so traumatized until seeing this. Thanks for sharing

[@MayankUpadhyaya-y2q]

Thank you for explaining the solution. you are really brilliant and extraordinary.

[@gary1614]

This is a very difficult question. Thank you for making this video. It makes a little bit more sense now. lol

[@sauravsingh4497]

Off topic but the discord link in the description Is not working (i wanted to join the server)

[@chaunceyzhang6595]

Thanks for your persistence do this video series!

[@GuruPrasadShukla]

great explaination man! keep going bro!

[@SiddharthReddy16]

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.

[@muhammadsodiqtoirov3204]

Thanks bro ! Good explanation Even gpt couldn't solve this problem ...

[@shashankjoshi8250]

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.

[@gnaneswarganta9920]

like what if we condensed the string first and later doing the computations

[@susmitsingh1775]

man fuck this problem, took me a bloody day to solve

[@pradyumnasingh9555]

thank you for such an easy explanation :)

[@shreyashpandey9351]

How will I be able to develop intuition like that?

[@chiragsrivastava4217]

class Solution: def getLengthOfOptimalCompression(self, s: str, k: int) -> int: @cache def dfs(i, k, prev, prev_count): if k

[@ish90917]

do we add cache evetime in question of DP or backtracking ? If not when do we add them ?

[@suhaanbhandary4009]

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).

[@pritz9]

To memoize the recursive solution, otherwise you are gonna get a TLE.

[@tranquoctoan1996]

Thank you, it saved me

[@krateskim4169]

Thank you so much

[@ronniey4231]

Can’t love your videos more😂

[@aybarskeremtaskan]

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.

[@Caramel-r9w]

How to do the opposite?

[@il5083]

Is using func_tools cache to save sometime a bad idea in an interview? (for memoization)

[@RolopIsHere]

I was allowed to use it, as long as you explain how it works...

[@w702897028970289]

What an explanation...

[@caothanhluan1813]

God tier explanation but TypeScript compiler says it TLE when using Map()😂😂😂

[@ngneerin]

I see hard and I quit I see medium and I watch I see easy and I solve

[@chaunceyzhang6595]

[@SmoothCode]

I relate so hard.

[@chien-yucode992]

So amazing

[@shubhamraj25]

The same solution in Python beat 79% of users for me

[@shreehari2589]

How the heck will I come up with this solution on spot in an interview, these problems are real tough

[@RajGupta-cu9hi]

How to convert it to 2-dp because some solve it in....?

[@aryakadam7892]

thank you

[@binitrajshah9354]

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?

[@thangavn8875]

phenomenal work, you gained a sub and a follower 💯

[@tanishq8211]

I dont understand why he did ... note updated the deleted character? can somebody explain?

[@0ManPiano0]

Don’t understand your question

[@racoon-thespy7062]

bruhh, in the morning doing the problem, guy has already got the solution ready, hats off

[@sidsudhir8231]

clutchhh

[@ajaybabua9735]

Can someone please explain me about the increment part 14:04 to 16:00?

[@w702897028970289]

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)

[@aswinnath8580]

your explanation helped me to understand that part.@@w702897028970289

[@w702897028970289]

I wrote it in Java version but 122/144 got TLE... Why

[@mindrust203]

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.

[@0ManPiano0]

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.

[@BTCSEDarshan]

Saviour !

[@SantoshKumar-bu2qr]

Why does he sounds like Bane (Batman) giving savage dialouges?

[@shawn_yg1394]

The example2 is indicating that minheap does not work but I still waste time for that...

[@shashankjoshi8250]

Nah. it will work for example 2. I tried it.. greedy passes 74 tc.

[@abhisheksuman4510]

This aproach is giving runtime error due to stack overflow.

[@shrn]

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

[@stat_life]

This solution had beaten 100% of users in runtime and memory, LEETCODE is broken

[@anonymousperson4466]

why is it so hard.....goddamn

[@0ManPiano0]

This one is hard, isn’t it.

[@anonymousperson4466]

@@0ManPiano0 I'm having a hard problem everyday...at least one.....this one's painfully hard for me

[@CheeseStickzZ]

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