Leetcode Daily | 1531. String Compression II

In this video I suggested an unusual way to look at the dynamic programming problems and why (and why not) a state can be valid. Hope you learn something new :)

*************************************************
Interview Experiences Playlists -

*********************************************************************

Please show support and subscribe if you find the content useful.

[samagrapathak]

and edge case me (equal - (k-removed)) negative aa gaya to ?

[lofibeats]

I was not able to understand the state first when I first saw the problem. The way you compare a problem with another similar problem is very unique and bring a lot of clarity.

[abdulshabbir]

This is the best explanation I’ve seen on a difficult DP problem. Thank you for taking the time to make this!

[kumarlakshya]

greatt jobbb mannn reallyyy u are the person that i have been looking for others just explain the solution u make us capable to arrive at solutionnn

[samagrapathak]

i think the extra edge case is required as base case is not hitting and it is very unintuitive

[samagrapathak]

please tell the condtions in which which that edge case will hit
except the all same chars case

[narolavarshil]

Another way is that we can use 3d dp and as k is at most 100 we can reduce it to k=10 as after 10 all are unnecessary and for k=100 we can special it out

[vaibhavkhanna]

Can you please tell what is the mistake in this tabulation approach ? My memoization code is running fine but I am not able to convert it to tabulation approach. If anyone can help please reply. Thanks

class Solution
{
public:
int s, int k)
{
dp(k + 2, + 1, vector<vector<int>>(27, vector<int>(101, -1))));
// i for k, j for index, l for previousCharacter and m for previousCount.

for (int i = 0; i < k + 2; i++)
{
for (int j = s.length(); j >= 0; j--)
{
for (int l = 0; l < 27; l++)
{
for (int m = 0; m < 101; m++)
{
if (i == 0)
{
dp[i][j][l][m] = INT_MAX;
}
else if (j == s.length())
{
dp[i][j][l][m] = 0;
}
else
{
int answer = INT_MAX;

answer = min(answer, dp[i - 1][j + 1][l][m]);

if (l + 'a' != s[j])
{
answer = min(answer, 1 + dp[i][j + 1][l][1]);
}
else if (m == 1 || m == 9 || m == 99)
{
answer = min(answer, 1 + dp[i][j + 1][s[j] - 'a'][m + 1]);
}
else
{
answer = min(answer, dp[i][j + 1][s[j] - 'a'][m + 1]);
}

dp[i][j][l][m] = answer;
}
}
}
}
}

return dp[k + 1][0][26][0];
}
};