【解決方法】誰かlong long ans=cal(s, k)-cal(s, k-1)のロジックを説明してもらえませんか?

プログラミングQA


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.

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

私が試したこと:

YouTubeでチュートリアルを見てみましたが、ロジックを理解できませんでした。

コメント

タイトルとURLをコピーしました