L7. Number of Substrings Containing All Three Characters | 2 Pointers and Sliding Window Playlist
Вставка
- Опубліковано 9 лют 2025
- Notes/Codes/Problem links under step 10 of A2Z DSA Course: takeuforward.o...
Entire playlist: • Two Pointer and Slidin...
Follow us on our other social media handles: linktr.ee/take...
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 hope striver one day i will build logic like you
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;
}
};
can you explain why you did => int count = plzhelp(s, k) - plzhelp(s, k - 1) ??
@@sauravdhar1696 kyo ki plzhelp(s,k) will return all substring having characters
@@Rahul_Mongia can this be avoided by making
count += (j - i + 1);
j++;
to
if(mpp(mp.size() == k){
count += (j - i + 1);
}
j++;
But Bro what is the guarantee that the the function you have written return the characters having only a,b,c which obvious count to because it may also return the count having aaa,aab,bba etc. does you have to say something.?
When you are writing "count += (j-i+1)" you are still using the SAME MINIMUM WINDOW CONCEPT. Earlier (j-i+1) used to signify the length of the substring, now it signifies the number of substrings(excluding the ones that have already been counted)
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
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
easy solution using the generic sliding window that we have used till here. Striver's solution is the best though:
TC= O(2N log3) at worst SC=O(3)
int n = s.length();
int left = 0 ;
int right = 0;
int counter=0;
map mpp;
while( right < n){
mpp[s[right]]++;
while(mpp.size() ==3){
counter+= n - right;
mpp[s[left]]--;
if(mpp[s[left]]==0) mpp.erase(s[left]);
left++;
}
right++;
}
return counter;
same idea i too got i for got that while
try to do it using hash array
will it work for string "aaacb" because at "aaacb" our while(mpp.size()==3) condition met when r will be at end (r==4) and after that r++ will make use out of loop and we can not count the substrings of left. So for "aaacb" we will get ans 1 but actual ans is 3
@@shubhamverma2737 There is a while loop while(mpp.size() ==3)
The left will shrink and again begin the process until map size is not equal to 3 i.e. there are not 3 characters in our substring
The bruteforce approach I do is
class Solution {
public:
int numberOfSubstrings(string s) {
int count = 0;
for(int i = 0; i
awesome explaination , these types of questions shows me how far i am from taking questions lightly.
Genuinely an incredible video solution. So easy to understand, and I wrote the code on my own after listening to your explanation. Subscribed, and thank you!
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
I was not able to understand this question's approach but you have done it :)
not watching the video i come to say i have done this question by myself with help of previous teaching thank u striver
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;
}
}
Your Solution is good , but it is failing in the 48 th test case in leetcode.
@@surendharv795 you need to use long becuase integer might overflow for larger tc
very good approach
//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
I did it using this way
best explanation! especially the part where you mentioned why even omiting the if checking would be ok, I was bamboozled haha
insane approach
Understood, thank you Striver!
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
}
How does res+=(r-l+1); gives u all the substrings, this way we used to calculate maxlen
i came to this same solution as well
Almost same:
My solution:
class Solution {
public:
int numberOfSubstrings(string s) {
int count = 0;
int l = 0, r = 0;
int acount = 0, bcount = 0, ccount = 0;
while(r < s.size()){
if(s[r]=='a')
acount++;
else if(s[r]=='b')
bcount++;
else
ccount++;
if(acount>0 && bcount>0 && ccount > 0){
int x = 0;
while(acount>0 && bcount>0 && ccount>0){
if(s[l]=='a')
acount--;
else if(s[l]=='b')
bcount--;
else
ccount--;
// count++;
x++;
l++;
}
count+=(s.size() - r) * x;
// l++;
}
r++;
}
return count;
}
};
what will be the complexity of this tho? O(N) or O(2N)?
i used a map but yeah since size is at max 3 , it wont be a problem
The optimised solution is a very clever sol
Another approach can be ans=all possible substring - string that contain a,b and c together
all possible substring = n(n+1)/2 and later one is easy to find using 2 pointers approach
This solution is ingenius.
Great Explanation!!
class Solution {
public:
int numberOfSubstrings(string s) {
int n = s.size();
int ans = 0;
vector arr(3,-1);
for(int i=0; i
class Solution {
public int numberOfSubstrings(String s) {
int map[]=new int[3];int count=0;
Arrays.fill(map,-1);
for(int i=0;i
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.
Mindblown
thank you bhayya
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!
NICE SUPER EXCELLENT MOTIVATED
int numberOfSubstrings(string s) {
int count = 0;
int left = 0;
int right = 0;
int size = s.size();
unordered_mapmp;
while(right < size)
{
mp[s[right]]++;
while(mp.size() == 3)
{
count += size - right;
mp[s[left]]--;
if(mp[s[left]] == 0) mp.erase(s[left]);
left++;
}
right++;
}
return count;
}
what a grate solution,just love this,thank u brother
Outstanding
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
}
}
thanks mate.
class Solution {
public int numberOfSubstrings(String s) {
int map[]=new int[3];int count=0;
Arrays.fill(map,-1);
for(int i=0;i
this was a tough one
bhai farishta h tu.
Literally 🔥✅
@@ayanahmad12 simp
@@ayanahmad12 simp
"UNDERSTOOD BHAIYA!!"
int numberOfSubstrings(string s) {
vector lastSeen(3,-1);
int cnt = 0;
for(int i=0; i
i didnt get what is lastseen[s[i] - 'a'] = i part can u please explain.
@@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
mind blown dude... crazy optimal soln
understood
The more easier solution can be finding the number of substrings that does not contain either of a,b or c and then subtract it with n*(n+1)/2 as done in previous ques.
class Solution {
public:
long long not_abc(string s){
int n=s.size();
int l=0,r=0,ans=0;
vector vec(3,0);
while (r0 && vec[1]>0 && vec[2]>0){
vec[s[l]-'a']--;
l++;
}
ans+=(r-l+1);
r++;
}
return ans;
}
int numberOfSubstrings(string s) {
int n=s.size();
return n*1LL*(n+1)/2-not_abc(s);
}
};
amazing logic!!!
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.
did you get the answer to your question?
@@ajithshetty1684have you got it???
@@ajithshetty1684 No one can give u that answer
class Solution {
public int numberOfSubstrings(String s) {
int n = s.length();
int l=0,r=0,count=0;
int lastSeen[] = {-1,-1,-1};
for(int i=0;i
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
Thanks
The series is dam good!! 🤍🤍💯
understood bhaiya
Please update the site also with all the upcoming videos 🙏
class Solution {
public:
int numberOfSubstrings(string s) {
int n = s.length();
int l=0;
int r=0;
int cnt = 0;
unordered_map mpp; //character and its frequency
while(r=3){
cnt = cnt + (n-r);
mpp[s[l]]--;
if(mpp[s[l]]==0) mpp.erase(s[l]);
l++;
}
if(mpp.size()
just small mistake in Brute force solution in if condition insted of adding them check if there all frq are greater than 0 if(hash[0] >0 && hash[1] >0 && hash[2] >0)
{
count++;
}
Is the bruteforce approach right?
bcos i dont think their sum being 3 be a valid check as repetition can lead to a false count
Understood. great
#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
Legit God
#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
Document link is not attached for some of the program
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]);
For one liner you can do : int ans = min({arr[0], arr[1], arr[2]});
@@AnujGupta-xi5ep ohhh, i was doin without the braces and was getting error, so i thought it wasn’t possible in cpp
My own O(2n) soln.
class Solution {
public:
int numberOfSubstrings(string s) {
// better approach
// sliding window
// let's see if it works.
// taking the variables
int n = s.length();
int l = 0, r = 0, cnt = 0, a = 0, b = 0, c = 0;
//checking from start to end
while(r < n){
if(s[r] == 'a') a++;
if(s[r] == 'b') b++;
if(s[r] == 'c') c++;
// if for a r and l, a >= 1, b >= 1, c >= 1, then for all following r and fixed l, the substring is valid
while(a>=1 && b>=1 && c>=1){
//we are checking till the l for which condition is valid, for that, we don't need to increase r, and add (n - r) to count for each while
cnt += (n - r);
if(s[l] == 'a') a--;
if(s[l] == 'b') b--;
if(s[l] == 'c') c--;
l++;
}
r++;
}
return cnt;
}
};
the example taken could have been better , as a,b,c is always together in the given example .
there is also an another approach where you generate all substrings which equals =n(n+1)/2 , and then form this result subtract the number of subarray that do not have a,b,c atleast once ( i.e (a>=1 && b>=1 && c>=1 ) should be false ,we have to find such array and subtract it from n(n+1)/2 ) .
Understood!
ak chis ish vedio sa patta chale he bhaiye ke fv colure yellow he 🙃🙃🙃🙃🙃.
Please upload note of the lecture on a2z sheet .
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
My question is what is your favorite colour
class Solution {
public:
int numberOfSubstrings(string str) {
int hash[256];fill(hash,hash+256,0);
int s=0,k=0,count=0;
int a='a',b='b',c='c';
while(k
from which platefrom this question belongs to
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
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;
}
Understood
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
Yeah, I think he meant to take the size of hashmap , hope you get it.
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.
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
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
@@ashnidahiya8347 setst
class Solution {
public int numberOfSubstrings(String s) {
int map[]=new int[3];int count=0;
Arrays.fill(map,-1);
for(int i=0;i
🧡
fabolous
I solved this ,this way it is easy appproach
class Solution {
public:
int numberOfSubstrings(string s) {
int a,b,c;
a=b=c=0;
int l=0;int r=0;
int len=0;
while(r=1 && b>=1 && c>=1){
// len++;
len=len +(s.length()-r);
if(s[l]=='a') a--;
else if(s[l]=='b') b--;
else if(s[l]=='c') c--;
l++;
}
r++;
}
return len;
}
};
he loves orange
class Solution:
def numberOfSubstrings(self, s: str) -> int:
a=-1
b=-1
c=-1
count=0
for i in range (len(s)):
char=s[i]
if char=='a':
a=i
if char=='b':
b=i
if char=='c':
c=i
if a!=-1 and b!=-1 and c!=-1:
count+=min(a,b,c)+1
return count
why we need to take minimum in these anyone explain please
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;
}
};
WoW!
UnderStood
❤👍
Your optimised code is really nice. but coming up with such kind of logic is something beyond my thinking. So I really don;t understand how to think like that.
minimal window 🫡🫡
My solution:
class Solution {
public:
int numberOfSubstrings(string s) {
int count = 0;
int l = 0, r = 0;
int acount = 0, bcount = 0, ccount = 0;
while(r < s.size()){
if(s[r]=='a')
acount++;
else if(s[r]=='b')
bcount++;
else
ccount++;
if(acount>0 && bcount>0 && ccount > 0){
int x = 0;
while(acount>0 && bcount>0 && ccount>0){
if(s[l]=='a')
acount--;
else if(s[l]=='b')
bcount--;
else
ccount--;
// count++;
x++;
l++;
}
count+=(s.size() - r) * x;
// l++;
}
r++;
}
return count;
}
};
what will be the complexity of this? O(N) only na?
20/01/25❤
unordered_map mp;
int l = 0,r=0,cnt = 0;
while(r=1 && mp['b']>=1 && mp['c']>=1){
cnt += s.size() - r;
mp[s[l]]--;
l++;
}
r++;
}
return cnt;
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
int numberOfSubstrings(string s) {
int ls[3] = {0, 0, 0};
int l = 0, r = 0, cnt = 0, n = s.size();
while (r < n) {
ls[s[r] - 'a']++;
while (ls[0] != 0 && ls[1] != 0 && ls[2] != 0) {
cnt += (n - r);
ls[s[l] - 'a']--;
l++;
}
r++;
}
return cnt;
}
demm man
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!
Yadi nhi smj aaya to code dekh ker dry run kero apne smj aa jayega
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
understood
Understood
int numberOfSubstrings(string s) {
vector lastSeen(3,-1);
int cnt = 0;
for(int i=0; i
understood
Understood
Understood