Click here to Skip to main content
15,886,873 members
Please Sign up or sign in to vote.
1.00/5 (4 votes)
See more:
Given a string of lowercase alphabets, count all possible substrings (not necessarily distinct) that have exactly k distinct characters.

Example 1:

Input:
S = "aba", K = 2
Output:
3
Explanation:
The substrings are:
"ab", "ba" and "aba".

Example 2:

Input:
S = "abaaca", K = 1
Output:
7
Explanation:
The substrings are:
"a", "b", "a", "aa", "a", "c", "a".

This is the code for above problem.

C++
class Solution
{
  public:
    long long int cal(string s,int k){
        int n = s.size();
        int freq[26] = {0};
        int dist_cnt = 0;
        long long int ans = 0;  //ans count
        
        int i=0;  //start of window
        int j=0;  //end of window
        while(j<n)
        {
            freq[s[j]-'a']++;
            if(freq[s[j]-'a'] == 1)
                dist_cnt++;
            
            //Decreasing the size of window
            while(dist_cnt > k)
            {
                freq[s[i]-'a']--;
                if(freq[s[i]-'a'] == 0)
                    dist_cnt--;
                i++;
            }
            j++;
            ans += (j-i+1);
        }
        return ans;
    }
    long long int substrCount (string s, int k) {
    	long long ans=cal(s,k)-cal(s,k-1);
    	return ans;
    }
};


What I have tried:

I have tried looking tutorials on youtube but couldn't able to grasp the logic.
Posted
Updated 25-May-23 5:21am
v2
Comments
Richard MacCutchan 25-May-23 11:02am    
Ask the person who wrote the code.
Graeme_Grant 25-May-23 18:51pm    
The output tells me what it is exactly doing, it is quite clear. But as Richard said, as this is someone else's code, you need to discuss it with them.
Member 15627495 26-May-23 0:58am    
long long int substrCount (string s, int k) {
    	 return cal(s,k)-cal(s,k-1);
    	// it's a substraction, providing the final difference value for a fixed 'k'. <- it's "answer"
        // try 'cal(s,k)' and try cal(s,k-1) alone by return.
        // it's math applying to get the number of answer ( a gap between k and k-1 )
        // 
    }

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900