3333. Find the Original Typed String II | Leetcode Daily Challenge | Dynamic Programming Hard

Check out the video of today's Daily challenge on Leetcode!
Subscribe for more cool stuffs.

Code Solution in text: See comments

Hi! I'm Mitadru Datta, IIT KGP'25. I love breaking down complex problems in simple words and hence the vision of this channel. Follow my channel with more upcoming content on interview experiences of various companies and in depth AI and DSA prep.

Hope you have an easy day ahead :)

#leetcode
#leetcodedaily
#leetcodedailychallenge
#dsa #potd #dynamicprogramming

[u-hfli]

at 15:16, shouldn't the expression sigma xi<k be sigma xi<k-min length, as we have already taken the min length as aur base string and we are just adding string to it...?

[Dakshgohil-]

the initial half was good explanation, but later the explanation became slight difficult

but thank u

[abhisheksharma]

Awesome explanation, really good. Thank you so much.

[vulcan]

to be honest i dont know if i didnt or i cant able to but i didn't understand the part that after the segment part and the adding the part to the original string...glad i able to learn to something from it ....

[ANKIT-moov]

Excellent explaination, gotta subscribe in my first watch of ur channel

[explorescience]

The core part of the problem is not cleared properly

[Nobel-sqw]

bhaiya aapse IIT hai aap IIT se nahi ho damn good explanation T_T.

[eyeonaianddsa]

#define ll long long
class Solution {
public:
ll md = 1e9 + 7;
int possibleStringCount(string word, int k) {
int n = word.size();
int cnt = 1, total = 1;
vector<int> seg;
for(int i=1;i<n;i++){
if(word[i]==word[i-1]){
cnt++;
}
else{
total = ((ll) total * cnt)%md;
seg.push_back(cnt-1);
cnt = 1;
}
}
//add the last segment
total = ((ll) total * cnt)%md;
seg.push_back(cnt-1);

int mnlen = seg.size();
if(k<=mnlen) return total;

k-=mnlen;

vector<ll> dp(k); dp[0] = 1;
//go thru seg
for(int x : seg){
vector<ll> pref(k); pref[0] = dp[0];
for(int i=1;i<k;i++){
pref[i] = (pref[i-1] + dp[i])%md;
}
for(int i=0;i<k;i++){
// naively i could have run another loop for the summation
// taking : 0, 1, 2 .... x elements
if(i-x-1>=0) dp[i] = (pref[i] - pref[i-x-1] + md)%md; // sum : dp[i] + dp[i-1] + .. + dp[i-x]
else dp[i] = pref[i] ;
}
}
//O(n + k^2 + k)
int invalid = 0;
for(int x : dp) invalid = (invalid + x)%md;
// >= k => total - (<k)
return (total - invalid + md)%md;
}
};

[siddhesh]

please explain in hindi so it will be easy to grasp..