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?

[@bhavikransubhe7244]

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

[@Drdarker]

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

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

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

[@Caramel-r9w]

How to do the opposite?

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

[@keremt8727]

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.

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

[@susmitsingh1775]

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

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

[@SantoshKumar-bu2qr]

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

[@gnaneswarganta9920]

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

[@tony7948]

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

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

[@urjeans2896]

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

[@stat_life]

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

[@gary1614]

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

[@caothanhluan1813]

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

[@w702897028970289]

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

[@shreehari2589]

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

[@abhisheksuman4510]

This aproach is giving runtime error due to stack overflow.

[@chiragsrivastava4217]

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

[@sauravsingh4497]

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

[@muhammadsodiqtoirov3204]

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

[@RajGupta-cu9hi]

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

[@sidsudhir8231]

clutchhh

[@shreyashpandey9351]

How will I be able to develop intuition like that?

[@il5083]

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

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

[@MayankUpadhyaya-y2q]

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

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

[@shubhamraj25]

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

[@tanishq8211]

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

[@0ManPiano0]

Don’t understand your question

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

[@pradyumnasingh9555]

thank you for such an easy explanation :)

[@chaunceyzhang6595]

Thanks for your persistence do this video series!

[@tranquoctoan1996]

Thank you, it saved me

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

[@w702897028970289]

What an explanation...

[@ronniey4231]

Can’t love your videos more😂

[@GuruPrasadShukla]

great explaination man! keep going bro!

[@aryakadam7892]

thank you

[@krateskim4169]

Thank you so much

[@chien-yucode992]

So amazing

[@BTCSEDarshan]

Saviour !

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

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

[@racoon-thespy7062]

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

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

[@thangavn8875]

phenomenal work, you gained a sub and a follower 💯