วีดีโอ

Will sum>0 always? I doubt. If sum becomes negative then we cannot use dp array

bhai solution ka link bhi attatch kr diya kro, Nice explanation👍👍

Like, Subscribe, Comment. Code: class Solution { public: int mod; long long solve(string &s, int index, vector<vector<vector<int> > > &dp, int sum, int w){ if(index==s.size()){ if(sum>s.size()){ return 1; } else{ return 0; } } if(dp[index][sum][w]!=-1){ return dp[index][sum][w]%mod; } if(w==0){ if(s[index]=='F'){ return dp[index][sum][w]=(solve(s,index+1,dp,sum, 1)%mod+solve(s,index+1,dp,sum+1, 2)%mod + solve(s,index+1,dp,sum-1, 3)%mod)%mod; } else if(s[index]=='W'){ return dp[index][sum][w]=(solve(s,index+1,dp,sum, 2)%mod+solve(s,index+1,dp,sum-1, 1)%mod + solve(s,index+1,dp,sum+1, 3)%mod)%mod; } else if(s[index]=='E'){ return dp[index][sum][w]=(solve(s,index+1,dp,sum, 3)%mod+solve(s,index+1,dp,sum-1, 2)%mod + solve(s,index+1,dp,sum+1, 1)%mod)%mod; } } else if(w==1){ if(s[index]=='F'){ return dp[index][sum][w]=(solve(s,index+1,dp,sum+1, 2) %mod+ solve(s,index+1,dp,sum-1, 3)%mod)%mod; } else if(s[index]=='W'){ return dp[index][sum][w]=(solve(s,index+1,dp,sum, 2)%mod+ solve(s,index+1,dp,sum+1, 3)%mod)%mod; } else if(s[index]=='E'){ return dp[index][sum][w]=(solve(s,index+1,dp,sum, 3)%mod+solve(s,index+1,dp,sum-1, 2)%mod )%mod; } } else if(w==2){ if(s[index]=='F'){ return dp[index][sum][w]=(solve(s,index+1,dp,sum, 1)%mod+ solve(s,index+1,dp,sum-1, 3)%mod)%mod; } else if(s[index]=='W'){ return dp[index][sum][w]=(solve(s,index+1,dp,sum-1, 1)%mod + solve(s,index+1,dp,sum+1, 3)%mod)%mod; } else if(s[index]=='E'){ return dp[index][sum][w]=(solve(s,index+1,dp,sum, 3)%mod+solve(s,index+1,dp,sum+1, 1)%mod)%mod; } } else{ if(s[index]=='F'){ return dp[index][sum][w]=(solve(s,index+1,dp,sum, 1)%mod+solve(s,index+1,dp,sum+1, 2)%mod )%mod; } else if(s[index]=='W'){ return dp[index][sum][w]=(solve(s,index+1,dp,sum, 2)%mod+solve(s,index+1,dp,sum-1, 1)%mod )%mod; } else if(s[index]=='E'){ return dp[index][sum][w]=(solve(s,index+1,dp,sum-1, 2)%mod + solve(s,index+1,dp,sum+1, 1)%mod)%mod; } } return 0; } int countWinningSequences(string s) { // vector<vector<int>> dp(s.size(),vector<int>(2001,-1)); mod=pow(10,9)+7; int n=s.size(); vector<vector<vector<int> > > dp( n, vector<vector<int> >(2*n+1, vector<int>(4,-1))); return solve(s,0 , dp, n, 0); } };

Superb man thanks

Amazing explanation. I also solved this question using a sliding window but couldn't figure out during the contest that if we find a substring with ≥ k consonants and subtract the substring with ≥ k+1 consonants, we can get the substring with exactly k consonants. I learned something new and won't forget this now. Thank you so much for making amazing videos. How do you figure out these tricks? I also want to learn them.

Thanks 🙏

bhai sbb kuchh to shi h bss ek doubt h clear krdo, ans += word.size() - j; means we are assuming agr hmme 0 to j tk condition satisfy ho gyi to baaki bache substring me bhi ho jaeggi but catche ye h ki hmme exactly k constant chahiye then how we can assume baki ke word.size() - j substring me k constant honge k se jyada hue to ?

" i " is the left pointer and " j " is right pointer, we will increment j till the point we are not satisfying our condition of having all vowels and k consonants and when the condition is satisfied we will increment i pointer ( which is left pointer ) till we are still satisfying the condition. Like, Subscribe, Comment if you have doubts. Subscribe !! class Solution { public: long long solve(string word, int k){ int i=0; int j=0; long long ans=0; map<char,int> mp; int cnt=0; while(j<word.size()){ if(word[j]=='a' || word[j]=='e' || word[j]=='i' || word[j]=='o' || word[j]=='u'){ mp[word[j]]++; } else{ cnt++; } // while(mp.size()==5 && cnt>=k){ ans+=word.size()-j; if(mp.find(word[i])!=mp.end()){ mp[word[i]]--; if(mp[word[i]]==0){ mp.erase(word[i]); } } else{ cnt--; } i++; } j++; } return ans; } long long countOfSubstrings(string word, int k) { return solve(word, k) - solve(word,k+1); // Leetcode Count of Substrings Containing Every Vowel and K Consonants II } };

Thanks buddy

Like, Subscribe, Comment. Subscribe !! Code: class Solution { public: int countOfSubstrings(string word, int k) { // a e i o u int ans=0; for(int i=0;i<word.size();i++){ int a=0,e=0,p=0,o=0,u=0,c=0; for(int j=i;j<word.size();j++){ if(word[j]=='a'){ a++; } else if(word[j]=='e'){ e++; } else if(word[j]=='i'){ p++; } else if(word[j]=='o'){ o++; } else if(word[j]=='u'){ u++; } else { c++; } if(a>0 && e>0 && p>0 && o>0 && u >0 && c==k){ ans++; } } } return ans; } };

bhai tu 8 min tak output ko hi leke chal raha hai logic toh taab pata chlalega na jab output aaya kaise woh baatega tu output ho hi justify kar raha hai ye baatana ki output aaise aaya

Saw a lot of videos overcomplicating this. simplest solution there is.

Very clear and amazing explanation. I figured out the first binary search since it’s a max-min type of question, but I couldn’t figure out the second one in the contest. But now its all clear. I’ll be looking forward to your video for the other weekly contest questions as well!

Thanks

badhiya

nhi samaj aya ,mere pas dimag nhi hai🤧🤧

Like , Subscribe, Comment. Don't forget to SUBSCRIBE !! Code : class Solution { public: int cal(int val, vector<long long > &pre, long long x){ long long l=0; long long r=pre.size()-1; int ans=-1; while(l<=r){ long long mid=l+(r-l)/2; if(pre[mid]*(long long )val<=x){ ans=mid; l=mid+1; } else{ r=mid-1; } } return ans; } bool check(int m, vector<int> &w, long long x,vector<long long > &pre){ // [2,1,1] //ith worker ne kitni h reduce kari x sec // 2,[1,3,6,10,,] // 2,6,12,12,.. // ans = 3 sec possible hai ? for(int i=0;i<w.size();i++){ int p=cal(w[i],pre,x); if(p!=-1){ m-=(p+1); } } if(m<=0){ return true; } return false; } long long minNumberOfSeconds(int m, vector<int>& w) { long long o=(long long )m*(long long )(m+1)/2; long long u=*max_element(w.begin(),w.end()); long long r=o*u; long long l=0; long long ans=pow(10,16); vector<long long > pre; pre.push_back(1); long long t=2; while(1){ if(pre.size()>m){ break; } pre.push_back(pre[pre.size()-1]+t); t++; } // pre = [1,3,6,10,15,21,...] while(l<=r){ long long mid=l+(r-l)/2; if(check(m,w,mid,pre)){ ans=mid; r=mid-1; } else{ l=mid+1; } } return ans; } };

Thank you, it would be really hard to come up with this on my own unless I ran through a lot of patterns

Didi what was your CGPA?

all testcases are passing but you do not perform bitwise AND, why??

bro one question is sorting the given array wont effect the absolute difference of orignal array

Can you please explain, why you took low as 0 for starting condition of Binary Search. Suppose you have array: [0, 4, 8] and d=1. Here the minimum valid difference shouldn't be: 4 I have doubt for this not being Monotonic in this way.

thank you for mentioning my channel 😊😊

The best video I found for this question. Huge shoutout!

not able to solve in contest 😭😭

Thanks

nice bro keep posting

Like! SUBSCRIBE! Comment! Below is the code : Code : class Solution { public: long long findMaximumScore(vector<int>& nums) { long long ans=0; int curr=nums[0]; int j=0; for(int i=1;i<nums.size();i++){ if(nums[i]>curr){ ans+=(long long )curr*(long long )(i-j); curr=nums[i]; j=i; } } if(j!=nums.size()-1){ ans+=(long long )curr*(long long )(nums.size()-1-j); } return ans; } };

Like! SUBSCRIBE! Comment! Below is the code : Code : class Solution { public: bool check(long long x, vector<long long> &start, int d){ long long curr=start[0]; for(int i=1;i<start.size();i++){ if(start[i]>curr+(long long )x){ curr=start[i]; } else if(curr+(long long)x <= (long long )start[i]+(long long )d){ curr = curr+x; } else{ return 0; } } return 1; } int maxPossibleScore(vector<int>& s, int d) { vector<long long > start; for(int i=0;i<s.size();i++){ start.push_back((long long )s[i]); } sort(start.begin(),start.end()); int l=0; int r=d+start[start.size()-1]-start[0]; int ans=0; while(l<=r){ long long mid=l+(r-l)/2; if(check(mid,start,d)){ ans=mid; l=mid+1; } else{ r=mid-1; } } return ans; } };

Nice Explanation bro👊

cant we have visited array rather than using masking?

I wrote recursive code for this same as house robber. Thanks

good video. Friendly feedback: the voice volume is low. I had to plug in my headphones. Had a question, in such dp questions, how do you first find the overlapping subproblems though? Maine input ke sath try kiya tha and also with some test cases i made up. i still couldn't find any overlaps at all. Har baar alag alag test cases ke trees banane padhenge ya we just wing it with the dp cache and hope there are overlaps? Contest mai kaise solve karen is type ke dp questions? Mujhe laga ye dp question hoga hi nahi kyunki i didnt any overlaps, i wasted 1 hour 15 mins of my contesst time trying to solve it with greedy. i got pretty close (502/563) test cases passed and it took me until today to figure out why greedy won't work. How do I improve at this?

Efforts 👍🏻👍🏻

Excellentttttt

Thank youuuuuuu

thanks mere sindhi bhai

Best explanation 👍

Perfect ❤

class Solution { public: void order(vector<pair<long long, long long>>& vec) { int n = vec.size(); for (auto& it : vec) { it.second = (it.second + (n - 1)) % n; } } long long minCost(vector<int>& nums, int x) { vector<pair<long long, long long>> vec; int n = nums.size(); for (long long i = 0; i < n; i++) { vec.push_back({nums[i], i}); } vector<long long> ans; for (auto& it : vec) { ans.push_back(it.first); } long long minm = accumulate(ans.begin(), ans.end(), 0ll); for (long long op = 1; op < n; op++) { order(vec); long long result = 0; for (int i = 0; i < n; i++) { long long val = vec[i].first; long long idx = vec[i].second; if (ans[idx] > val) { result += val; ans[idx] = val; } else { result += ans[idx]; } } result += (long long)(op * x); minm = min(result, minm); } return minm; } };

You'll get MLE on this solution

Amazing explaination

Good explanation sir.

👎👎👎

so smooth bro,nicely done😁😁😁

bhai video ekdum bdia hai par voice mai thoda issue tha difficulty horhi ha samajhne mai thodi

Great

no need to use max in first and third if, btw good solution

what is rans

Subscribe !! Like !! Comment !! Code : class Solution { public: long long solve(vector<int> &nums, vector<vector<long long >> &dp, int index, int choice){ if(index==nums.size()){ return 0; } if(dp[index][choice]!=INT_MIN){ return dp[index][choice]; } if(choice==0){ return (long long )nums[index]+solve(nums, dp, index+1, 1); } long long newS= (long long )nums[index]+solve(nums, dp, index+1, 1); long long cont = (long long )(-nums[index])+solve(nums, dp, index+1, 0); return dp[index][choice] = max(newS,cont); } long long maximumTotalCost(vector<int>& nums) { vector<vector<long long >> dp(nums.size(),vector<long long > (2,INT_MIN)); return solve(nums, dp, 0, 0); } };