[ad_1]
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でチュートリアルを見てみましたが、ロジックを理解できませんでした。
[ad_2]
コメント