L7. Number of Substrings Containing All Three Characters | 2 Pointers and Sliding Window Playlist 

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

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; } };

i hope striver one day i will build logic like you

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; } }

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

I was not able to understand this question's approach but you have done it :)

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

insane approach

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 }

The optimised solution is a very clever sol

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

what a grate solution,just love this,thank u brother

best explanation! especially the part where you mentioned why even omiting the if checking would be ok, I was bamboozled haha

amazing logic!!!

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!

Outstanding

Understood. great

Thanks

mind blown dude... crazy optimal soln

Please update the site also with all the upcoming videos 🙏

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.

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.

Understood!

The series is dam good!! 🤍🤍💯

bhai farishta h tu.

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

Document link is not attached for some of the program

Legit God

WoW!

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; }

❤👍

fabolous

My question is what is your favorite colour

int numberOfSubstrings(string s) { vector lastSeen(3,-1); int cnt = 0; for(int i=0; i

demm man

#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

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

#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

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; } };

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

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

viewed multiple times .. but your explanation is not good .. sorry to say!

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]);

int numberOfSubstrings(string s) { vector lastSeen(3,-1); int cnt = 0; for(int i=0; i