String Compression II - Leetcode 1531 - Python

0:00 - Read the problem
0:12 - Drawing Explanation
10:19 - Coding Explanation

leetcode 1531

#neetcode #leetcode #python

[MP-nyep]

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

[s]

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

[bhavikransubhe]

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

[tony]

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

[SiddharthReddy]

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.

[gary]

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

[urjeans]

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

[MayankUpadhyaya-yq]

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

[muhammadsodiqtoirov]

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

[ujjwalmaheshwari]

class Solution {
map<vector<int>, int>dp;

int solve(string &s, int k, int i, char prev, int prevCnt){

if(k<0)
return INT_MAX;
if(i==s.size())
return 0;

vector<int>temp = {k, i, prev, prevCnt};
if(dp.find(temp) != dp.end())
return dp[temp];

int ans = INT_MAX;
if(s[i]==prev){
int inc = 0;
if(prevCnt==1 || prevCnt==9 || prevCnt==99)
inc = 1;
int ans1 = inc + solve(s, k, i+1, prev, prevCnt+1);
ans = ans1;
// int ans2 = INT_MAX;
// if(prevCnt==1 || prevCnt==9 || prevCnt==99)
// ans2 = solve(s, k-1, i+1, prev, prevCnt);
// ans = min(ans1, ans2);
// it is working without taking delete case - as delete case has been taken when curr comes first time in optput string & at that time curr!=prev & we have taken delete case
}
else{
int ans1 = 1+solve(s, k, i+1, s[i], 1);
int ans2 = solve(s, k-1, i+1, prev, prevCnt);
ans = min(ans1, ans2);
}

return dp[temp] = ans;
}

public:
int s, int k) {

return solve(s, k, 0, 0, 0);

}
};


nice explanation brother but it is giving tle

[chaunceyzhang]

Thanks for your persistence do this video series!

[chiragsrivastava]

class Solution:
def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
@cache

def dfs(i, k, prev, prev_count):
if k<0:
return float("inf")
if i==len(s):
return 0
if s[i]==prev:
increment=1 if prev_count in [1, 9, 99] else 0
res=increment+dfs(i+1, k, prev, prev_count+1)
else:
res=min(
dfs(i+1, k-1, prev, prev_count),
1+dfs(i+1, k, s[i], 1)
)
return res
return dfs(0, k, "", 0)
using inbuilt cache significantly improves runtime
Runtime
1488ms
Beats95.00%of users with Python3

[pradyumnasingh]

thank you for such an easy explanation :)

[GuruPrasadShukla]

great explaination man!
keep going bro!

[shubhamraj]

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

[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 (25 times a) and the k is 20, then we need to delete so that it is not a25, but a5 instead.

[ngneerin]

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

[caothanhluan]

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