Count number of substrings with exactly k distinct characters | GeeksforGeeks

This video is contributed by Ishmeet Kaur

Please Like, Comment and Share the Video among your friends.

Install our Android App:

Follow us on Facebook:

And Twitter:

Also, Subscribe if you haven't already! :)

[samratganguly]

Not only for this video in every question's explanation videos the contributors just read the slides line by line . I know English and I can read them too..but what's the advantage if we don't learn how to build the logic ...so this type of videos are not needed, really .

[nupurchoudhary]

Change this content.. I can read I need someone to explain

[Kaivalyamani]

They dont explain properly on youtube because they want to sell their course

[HabibRahman-zddt]

explaining O(n^2) solution
1. there are two nested loop to get all possible substring, first loop is to set "i" the leftmost position of substring and 2nd loop is setting 'j' the rightmost position of substring on each iteration.
2. there is a variable named "dist_count" that counts total number of distinct character that current substring has.
3. there is an array "cnt" of size 26. this array counts the number of occurrence of each character in each substring. so if we iterate through the array, we would know which character occurs how many times.
4. How "cnt" array stores number of occurrence of each character ? well, we know each character has ascii value and the given string contains only lower case alphabets. so if we do little subtraction 'a'-'a' it gives us 0, 'b'-'a' = 1, 'c'-'a' = 2 'z'-'a' = 25. So if we substract each character by 'a' we would get a integer from 0-25 range. We can use the integers as array index for each character.
so if a character appears in substring, we need to substract that character by 'a' and increase the index of array accordingly. So if cnt[0] = 3, it means character 'a' occurs 3 times

5. the rest of tasks are simple, while updating "cnt" if current index's value is equal to 0, that means the character occurred first time, increase dist_count by 1.
6. if distinct character count is equal to K, that means current substring has exactly k distinct characters. Increase res variable by 1
7. after all the iteration res variable contains total number of substring count that has k distinct characters

[poojamehta]

uff why geekforgeeks organisation is degrading their videos quality by giving this girl to explain the videos as she is just reading the video no explanation
its really irritating
Replace her please

[sahilgupta]

according to question constraints we can maximum use nlogn

[schin_verma]

and this code get failed for multiple taste cases

[anantmouraya]

But we need constant space complexity as
Mentioned in question

[superchillho]

tragic.. just got this in an interview and did not get it

[nayanakbari]

Just reading, no explaination no dry run then what is the use of making videos that too on the gfg channel

[yobro]

Ooh that was very much selfish nature of that girl..

[nidhitiwari]

where is the hashtable that she mentioned in the beginning :/

[letscodewithshivam]

stop posting such videos gfg, we dont want to hear these robotic voices just upload proper explaination to conceptualize the problems,

[itsmerahulsoni]

Why you are reading and spoiling the explanation

[algorithmimplementer]

I am horrified by the sexist comments below. Seriously? When you cannot put a little more effort to solve this problem all by yourself without watching video, I wonder how you can judge other people and their help to help you out. Clearly shows some lack of self respect.

[jayjethva]

Please replace this girl no explanation only reading the code..

[gauravkumartiwari]

Pathetic quality of video.
You guys just paste the solution and just read out the code.
Dekho reading hum bhi kar sakte hai, explain kar sakte ho to karo.

[trending]

Inse bekaar youtube koi nai explain karta hai

[viditvaish]

bahut hi wahiyat tarika hai batane ka isse sahi mat batao