Count Number of Homogenous Substrings | Intuition | Math | Leetcode - 1759

This is the 24th Video on our String Playlist.
In this video we will try to solve a very good Greedy Problem - Count Number of Homogenous Substrings (Leetcode -1759).

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Count Number of Homogenous Substrings
Company Tags : will update soon

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook

[avishkarrangari]

i literally understand as soon as you go through half of the intitution
thanks for the explanation 😁.

[Ramneet]

It was really easy

Int ans=0;
Int mod=1e9+7;
Int i=0;
For(int j=0;j<n;j++){
If(a[i]!=a[j]){
i=j;
}
ans=(ans+(j-i+1))%mod;
}
Return ans;

[kamoleshroy]

I solved this by running a for loop, if s[ i ] == s[ i+1 ] then count++ else ans += count*(count+1)/2.

Loved the way of your implementation, Thanks🥰

[FanIQQuiz]

I was able to solve on my own. All credit goes to you sir. Thank you

[YashMalav-khov]

After completing your sliding window playlist i did this by sliding window concept❤thanks

[hypewaali]

You are just awesome 🙌. This teaching level is unmatched

[varunaggarwal]

I was confused between recursion and loop but I eliminated recursion as it is best when it comes to subsequence, thanks for the explanation.

[mohammadaftabansari]

Thanks for the smooth explanantion....!

[swastik]

i, ln, count = 0, 0, 0

mod = (10**9) + 7

n = len(s)

while i < n -1 :

if s[i] != s[i+1]:

ln += 1
count += (ln*(ln+1))//2
ln = 0
i += 1

else:

ln += 1
i += 1

count += ((ln+1)*(ln+2))//2

return count%mod

[Sawlf]

I really like the way you explain every question. I personally am still facing a lot of difficulties in subset, subsequence problems using recusion so it would be really helpful if u can make a video dedicated to just these topics 😊

[dhruvrawat]

class Solution {
#define ll long long
public:
int countHomogenous(string s) {
ll mod = 1e9 + 7;
ll n = s.size();
if(n == 1){
return 1;
}
ll count = 1;
ll fa = 0;
for(ll i = 1; i < n; i++){
if(s[i] == s[i-1]){
count++;
}
else{
fa += ((count)*(count+1))/2;
fa = fa%mod;

count = 1;
}
}

fa += ((count)*(count+1))/2;
fa = fa%mod;

return fa;
}
};

[ashwanisharma]

Aaj maja aagya bhidu apne aap se solve kiya
@codestorywithMIK sir ko aaram meri tarf se. 😉😁

class Solution {
public:
int mod = 1e9+7;
int countHomogenous(string s) {

long long mod = 1e9+7;
int i=0;
int ans=0;
for(int j=0;j<=s.size();j++){
if(s[j]!=s[i]){
long long n = j-i;
i=j;
ans+=((n*(n+1))/2)%mod;
}
}
return ans%mod;
}

TC --> O(N)
SC --> O(N)

[CodeZipper]

class Solution {
public:
const int mod = 1e9+7;
int countHomogenous(string s) {

s+='#';
unordered_map<string, int>m;
int count=1;
for(int i=1;i<s.size();i++){
if(s[i-1]!=s[i]){
int unique=i-1;
string temp = string(count, s[i-1]) + to_string(unique);
m[temp]=count;
count=1;
}
else count++;
}

long long sum=0;
for(auto t:m){

int size = t.second;

for(int i=1;i<=size;i++){
if(i==1) sum += size;
else if(i==size) sum += 1;
else sum += (size-i+1);
}

}

return sum%mod;


}
};

[ammanchhetri]

got the intuition just after saw that it is based on i was solving it using map...

[dhairyachauhan]

very basic question, such questions are solved using the atlmost sliding window trick. If you cant think of any solution you should think of the atmost trick,
dont know it? then do read about it, it was well written by lee

the basic idea is no. of substring having exactly k different characters = no. of substrings having 0->k different character - no. of substring having 0->k-1 different characters.

why?
s(k) = s(1) + s(2) +
s(k-1) = s(1) + s(2)
on cancelling both equations you are left with no. of stings with exactly k characters

here k = 1 hence s(k) = s(1) and s(k-1) = s(0) which is 0
note: k is the no. of different characters present in the string

code

```
class Solution {
public:
int mod = (int)1e9+7;
int solve(string s, int k){

vector<int>mp(26, 1);
int i = 0;
int j = 0;
int n = s.length();
int required = 0;
long long count = 0;
while(j<n){
char ch = s[j]-'a';
mp[ch]--;
if(mp[ch] == 0){
required++;
}
while(required>1){
char ch = s[i]-'a';
mp[ch]++;
if(mp[ch] == 1){
required--;
}
i++;
}
count = (count + j-i+1)%mod;
j++;
}
return count;
}

int countHomogenous(string s) {
return solve(s, 1);
}
};
```

[parthbhatti]

When I started thinking about this problem, I was thinking about generating sub strings. How did you think about this problem? meto soch hi nhi pa rha that different and when i start your video from very first dry run i just get the code in my mind and intuition.

[floatingpoint]

I think you solved a similar problem before but i do not remember. does anyone knows it?

[dayashankarlakhotia]

public int countHomogenous (String s){
int
int ans=0, cnt=0;
char cur='#';
for(char c:s.CharArray ()){
cnt+=c==cur?cnt+1:1;
cur=c;
ans+=cnt;
ans%=mod;
}
return ans;
}
tc=0(n);
sc=0(1);
🎉❤

[tanishqdawar]

hey sir! i solved this question my 82 testcases works but got error in testcase 83
the code is below can you tell me my mistakee
class Solution {
public:
int Mod = 1e9 + 7;
int countHomogenous(string s)
{
int ans =0;
string text="";
int i=0;
while(i!=s.size())
{
text+=s[i];
if(s[i]!=s[i+1])
{
ans+=text.size();
text = "";
}
else
{
ans+=text.size();
}
i++;
}
return ans%Mod; }
};