Notes/Codes/Problem links under step 10 of A2Z DSA Course: takeuforward.org/strivers-a2z... Entire playlist: • Two Pointer and Slidin... Follow us on our other social media handles: linktr.ee/takeuforward
Пікірлер: 72
@artofwrick4 ай бұрын
These questions are very important for contests . The first question is always a string question where you have to generate subarray. For arrays, questions from PREFIX sum comes often
@namannema33493 ай бұрын
i hope striver one day i will build logic like you
@mayank_singh_43Ай бұрын
This problem of counting substring and subarrays always confused me in any contest , now I learned the concept of how to do this. THanks a lot striver bhaiya
@sauravkumar-ln7zhАй бұрын
i did this question based on the logic based on previous question → We need to monitor every character in the sliding window. → For this, we use a map to keep track of the number of each character present in the sliding window. → If the number of distinct characters exceeds k, we start removing characters from the back until the size of the map is less than or equal to k. → If the count of a certain character becomes zero while removing it from the back, we must erase it from the map to decrease the map's size. class Solution { public: int plzhelp(string s, int k) { int i = 0; int j = 0; unordered_map mp; int count = 0; while (j < s.length()) { mp[s[j]]++; while (mp.size() > k) { mp[s[i]]--; if (mp[s[i]] == 0) { mp.erase(s[i]); } i++; } count += (j - i + 1); j++; } return count; } int numberOfSubstrings(string s) { int k = 3; int count = plzhelp(s, k) - plzhelp(s, k - 1); return count; } };
@sauravdhar1696Ай бұрын
can you explain why you did => int count = plzhelp(s, k) - plzhelp(s, k - 1) ??
@Rahul_MongiaАй бұрын
@@sauravdhar1696 kyo ki plzhelp(s,k) will return all substring having characters
@bhargav.v.m.193Ай бұрын
@@Rahul_Mongia can this be avoided by making count += (j - i + 1); j++; to if(mpp(mp.size() == k){ count += (j - i + 1); } j++;
@user-kx1sv7lq4k2 ай бұрын
I was not able to understand this question's approach but you have done it :)
@2amCoder4 ай бұрын
the reason you were good at cp. i tried many things with this solution but none of them were close good as this last explanation
@ManishKumar-dk8hl4 ай бұрын
optimal :- class Solution { public int numberOfSubstrings(String s) { int len=0; int r=0; int[] arr=new int[3]; Arrays.fill(arr,-1); while(r
@ratishjain27184 ай бұрын
insane approach
@cheezy_cheez2 ай бұрын
best explanation! especially the part where you mentioned why even omiting the if checking would be ok, I was bamboozled haha
@Adarsh-fg5gs2 ай бұрын
i did somewhat diffrent as TOtal no of subarrays - subarrays with at most 2 distinct characters and it becomes same as previous question int countSubstring(string s) { //Total no of subarrays with n characters =n(n+1)/2 int n=s.size(); int total=n*(n+1)/2; //now write code to find for at most 2 distinct characters int acnt=0,bcnt=0,ccnt=0,res=0,l=0,r=0; while(r0 && bcnt>0 && ccnt>0){ if(s[l]=='a')acnt--; if(s[l]=='b')bcnt--; if(s[l]=='c')ccnt--; l++; } res+=(r-l+1); r++; } return total-res; //total no of subarrays-subarrys with at most two distinct }
@rlm3227Ай бұрын
The optimised solution is a very clever sol
@sunitsable27523 ай бұрын
amazing logic!!!
@ganeshjaggineni4097Ай бұрын
NICE SUPER EXCELLENT MOTIVATED
@moonlight-td8edАй бұрын
mind blown dude... crazy optimal soln
@Arya200123 ай бұрын
what a grate solution,just love this,thank u brother
@abhinayrk9852 ай бұрын
Outstanding
@sobhansahoosubh3873Ай бұрын
we also do like this way int numberOfSubstrings(string s) { int n = s.size(); int l = 0,r = 0,count = 0; unordered_map mp; while(r < n) { mp[s[r]]++; while(mp['a'] >= 1 && mp['b'] >= 1 && mp['c'] >= 1 ) { count = count + (n - r); mp[s[l]]--; l++; } r++; } return count; }
@codeman38283 ай бұрын
Understood. great
@subee1284 ай бұрын
Thanks
@KratiGarg-ue1ph2 ай бұрын
I tried the approach you gave in the binary subarray question (number of total subarrays(n*(n+1)/2) - the subarrays where mapcount < 3. that also worked. Please give tips on how to approach a question like this!
@tanishqtyagi14652 ай бұрын
The series is dam good!! 🤍🤍💯
@rajalakshmis73083 ай бұрын
Thank you, Striver. Before watching this video, I just solved it using your previous lecture pattern. But, the approach you used is the best among all. import java.util.HashMap; public class Solution { public static int countSubstring(String s){ // Write your code here. // to find the tot subarray count int res = s.length()*(s.length()+1)/2; // return tot subarray - subarray which has atmost any 2 characters from a,b,c. return res-solve(s); } // function to find a subarray which has atmost any 2 character from a,b,c public static int solve(String s){ HashMap map = new HashMap(); int left=0,count=0; for(int right=0;right2){ map.put(s.charAt(left), map.get(s.charAt(left))-1); if(map.get(s.charAt(left))==0) map.remove(s.charAt(left)); left++; } count+=right-left+1; } return count; } }
@surendharv79513 күн бұрын
Your Solution is good , but it is failing in the 48 th test case in leetcode.
@techyguyaditya4 ай бұрын
This took a bit of time to understand for optimal approach. I was literally trying to derive mathematical formula which only passes the test case shown in video, further optimizing the code. But the edge case is that, L may not update in other test cases. Basic approach: Find left value of minimum sliding window in each iteration (start finding once a,b,c gets it's value other than -1). Then basically, for each iter, ctr += 1 + L (where L is leftmost index of window, min(a,b,c)). Striver said to omit if statement, because 1 + (-1) = 0. I disagree with that, because if you see low level programming, the unnecessary write operation happens to the memory even if the value remains the same. Write operations are generally considered as costly operation. Even if it's for 1 extra line of code, it will prevent the costly write operation just by having read operation, further optimizing the code.
@akay579716 күн бұрын
Mindblown
@saurabhchaudhari415728 күн бұрын
//Another Optimized Approach class Solution { public: int numberOfSubstrings(string s) { int n=s.length(); int cnt=0; int left=0; int right=0; unordered_mapmpp; while(right
@aamna52434 ай бұрын
bhai farishta h tu.
@ayanahmad124 ай бұрын
Literally 🔥✅
@PawanKumar-tj2xkАй бұрын
@@ayanahmad12 simp
@ujjwalkashyap91964 ай бұрын
Please update the site also with all the upcoming videos 🙏
@shivisingh99753 ай бұрын
Understood!
@square-kstudios95613 ай бұрын
Great explanation! How does one come up with a solution like this in the constraints of an interview though, if we haven't seen it ever in the past? Some companies only give you 15 mins to come up with a solution, explain it, dry run it, code it and then provide the time/space complexity.
@ajithshetty16842 ай бұрын
did you get the answer to your question?
@dipendrasingh48744 ай бұрын
thank you bhaiya ... please tcs nqt segment i was solving them but u removed that from site .....(or i am not able to find it )please add thank you
@shashankvashishtha445418 күн бұрын
understood
@RonitTejaniАй бұрын
Legit God
@rushidesai283613 күн бұрын
This looks more like CP question rather than an interview question.
@adityapandey234 күн бұрын
Understood
@AkOp-bf9vm15 күн бұрын
the line if(hash[0]!=-1 && ...) is not compulsory, the code will work fine without this line because -1+1=0 and if 0 is added to Count it didn't impact the answer
@Flash-qr5oh2 ай бұрын
WoW!
@rider558413 күн бұрын
here is the java code = class Solution { public int numberOfSubstrings(String s) { // Array to store the latest positions of characters 'a', 'b', and 'c' int[] latestPosition = new int[] {-1, -1, -1}; // This will hold the count of valid substrings int answer = 0; // Iterate over each character in the string for (int i = 0; i < s.length(); ++i) { char currentChar = s.charAt(i); // Update the latest position of the current character latestPosition[currentChar - 'a'] = i; // Find the smallest index among the latest positions of 'a', 'b', and 'c' // and add 1 to get the count of valid substrings ending with the current character int minPosition = Math.min(latestPosition[0], Math.min(latestPosition[1], latestPosition[2])); answer += minPosition + 1; } return answer; // Return the total count of valid substrings } }
@socify44102 ай бұрын
fabolous
@saakshishekhar2374 ай бұрын
int numberOfSubstrings(string s) { vector lastSeen(3,-1); int cnt = 0; for(int i=0; i
@sakethsenapathi83234 ай бұрын
i didnt get what is lastseen[s[i] - 'a'] = i part can u please explain.
@ManishKumar-dk8hl4 ай бұрын
@@sakethsenapathi8323 s[i] character represent kr raha h aur jb unme 'a' minus hoga too a-a=0 ; b-a=1 ;c-a =2 ayega then lastseen wali array k index pr string k character ka index store hoyega . index 0 of array=a, index 2= b,index 2=c
@animexworld66144 ай бұрын
My question is what is your favorite colour
@angeldeveloper4 ай бұрын
❤👍
@adilkevin62203 ай бұрын
Document link is not attached for some of the program
@expanse884614 күн бұрын
Another solution using previous video method class Solution { public: int numberOfSubstrings(string s) { vectorhashh(3,0); int l=0,r=0,n=s.size(); int ct=0; // vectordis; while(r0 && hashh[1]>0 && hashh[2]>0) { ct+= n-r; hashh[s[l]-'a']--; // dis.push_back(ct); l++; } r++; } // for(int i=0;i
@nirbhaysingh79714 ай бұрын
#include int countSubstring(string s){ // Write your code here. int n = s.size(); int left = 0; int right = 0; map mpp; int cnt = 0; while(right
@omkarsawant9267Ай бұрын
#include #include #include #include using namespace std; // Function to count the number of substrings containing all three characters 'a', 'b', and 'c' pair numberOfSubstrings(string s) { // Hashmap to store the count of 'a', 'b', and 'c' in the current window unordered_map count; int left = 0, result = 0; vector substrings; // Iterate over the string with 'right' as the end of the window for (int right = 0; right < s.length(); ++right) { // Increment the count of the current character count[s[right]]++; // Check if all three characters are present in the current window while (count['a'] > 0 && count['b'] > 0 && count['c'] > 0) { // If yes, add all possible substrings starting from the current 'left' to 'right' result += s.length() - right; // Capture the substrings for (int k = right; k < s.length(); ++k) { substrings.push_back(s.substr(left, k - left + 1)); } // Move the left end of the window to the right count[s[left]]--; left++; } } return {result, substrings}; } int main() { string s = "abcabc"; auto result = numberOfSubstrings(s); cout
@CE_113_Katyayni3 ай бұрын
sir your brute force approach is actually wrong because when we sum the hash[0]+hash[1]+hash[2] ==3 here it may be the case that hash[1]=0 and hash[0]=2 in this case also the if state would be true and cnt will increase which is actually wrong
@rohitvishwakarma70463 ай бұрын
Yeah, I think he meant to take the size of hashmap , hope you get it.
@azizkavas69933 ай бұрын
No such case is possible because hash doesnt count the number of occurance instead it just sign the related index. If you try yourself with sample code you will see what I mean. Kind regards.
@ashnidahiya8347Ай бұрын
This is a brute force approach using sets, hope it helps: int countSubStrings(string str, int k) { set st; int count = 0; int n = str.length(); for(int i=0;i
@sparksfly4421Ай бұрын
his code in brute force is correct. The hash array only gets assigned a truthy value (1) at the index of the given alphabet (where index(a) = 0, index(b)=1, index(c)=2) if it happens on the given letter in the string. It can never increment beyond that since it's an assignment operator
@doremon810722 ай бұрын
demm man
@user-fw4kz3bb4g2 ай бұрын
EASIEST APPROACH (C++) class Solution { public: int numberOfSubstrings(string s) { int left=0, right=0,count=0; vectorarr(3,0); while(right0 && arr[1]>0 && arr[2]>0){ count+=s.size()-right; arr[s[left]-'a']--; left++; } right++; } return count; } };
@Bhai98664 ай бұрын
public int numberOfSubstrings(String s) { int[] lastSeen = new int[3]; Arrays.fill(lastSeen, -1); int cnt = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); lastSeen[c - 'a'] = i; if (lastSeen[0] != -1 && lastSeen[1] != -1 && lastSeen[2] != -1) { cnt += (1 + Math.min(lastSeen[0], Math.min(lastSeen[1], lastSeen[2]))); } } return cnt; }
If someone can debug this solution then they are real genius class Solution { public: int numberOfSubstrings(string s) { map map; int l = 0; int r = 0; int count = 0; int minValue=0; while (map.size() != 3) { map[s[r]] = r; r++; } while (r < s.length()) { minValue=INT_MAX; for (const auto& pair : map) { cout
@ShubhamMIshra-hv5nz3 ай бұрын
CODE FOR THEOPTIMISED SOLUTION!!!!! class Solution { public: int numberOfSubstrings(string s) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int count =0; int length=s.size(); int lastSceen[3]={-1,-1,-1}; for(int i =0; i < length; i++){ lastSceen[s[i]-'a']=i; if(lastSceen[0] != -1 && lastSceen[1]!= -1&& lastSceen[2]!=-1) { count += min(lastSceen[0],min(lastSceen[1],lastSceen[2])) +1; } } return count; } }; whats up??
@user-zm6nk5mw9i15 күн бұрын
i wrote a O(n) code but it gives only 36% better i dont know why and how can i improve it further? class Solution { public: int numberOfSubstrings(string s) { int l=0; int n=s.size(); unordered_map index; int ans=0; for(int r=0;r
@anmolvanced3262Ай бұрын
viewed multiple times .. but your explanation is not good .. sorry to say!
@KartikeyTT4 ай бұрын
If you want to find minimum of three elements in cpp. You can do it like this- int temp = min(arr[0],arr[1]); int lowestI = min(temp, arr[2]);
@AnujGupta-xi5ep3 ай бұрын
For one liner you can do : int ans = min({arr[0], arr[1], arr[2]});
@KartikeyTT3 ай бұрын
@@AnujGupta-xi5ep ohhh, i was doin without the braces and was getting error, so i thought it wasn’t possible in cpp
@adityababu3405Ай бұрын
int numberOfSubstrings(string s) { vector lastSeen(3,-1); int cnt = 0; for(int i=0; i