至少包含前K个字母一次的子串计数

#include <bits/stdc++.h>
using namespace std;

int numberOfSubstrings(string alpha, int K) {
   // Finding all substrings of the alpha
   vector<string> subStr;
   for (int p = 0; p < alpha.size(); p++) {
      for (int q = 1; q <= alpha.size() - p; q++) {
         // Get substring from p to q
         subStr.push_back(alpha.substr(p, q));
      }
   }
   // Counting the number of substrings containing all K characters
   int result = 0;
   for (int p = 0; p < subStr.size(); p++) {
      // To store the frequency of characters in the current substring
      map<char, int> freq;
      // To store the totally different characters
      int chars = 0;
      // Traverse substring
      for (int q = 0; q < subStr[p].size(); q++) {
         // If a character does not exist in the map, increment chars
         if (freq[subStr[p][q]] == 0) {
            freq[subStr[p][q]]++;
            chars++;
         }
      }
      // If different chars are the same as K, the string is valid.
      if (chars == K) {
         result++;
      }
   }
   return result;
}
int main() {
   string alpha = "abcdda";
   int K = 4;
   cout << "The number of substrings containing all K characters at least once is " << numberOfSubstrings(alpha, K);
   return 0;
}

#include <bits/stdc++.h>
using namespace std;

int numberOfSubstrings(string alpha, int K) {
   // For storing the frequency of characters
   unordered_map<char, int> freq;
   int left = 0, right = 0, len = alpha.size(), cnt = 0;
   // Traveres the string
   while (right < len) {
     // Update character frequency
     freq[alpha[right]]++;
     // If the size of the map contains all K characters
     if (freq.size() == K) {
       // Traverse the map until the map size is k
       while (freq.size() == K) {
         // Add all valid substrings.
         // If (left, right) contains all K characters, (left, right + 1), (left + right + 2), ...  also contains.
         cnt += len - right;
         // Update character frequency
         freq[alpha[left]]--;
         // Remove the character if its frequency is 0.
         if (freq[alpha[left]] == 0)
            freq.erase(alpha[left]);
         // Move to the next character from left
         left++;
       }
       // Increment the right pointer.
       right++;
     }
     // Increment right by 1
     else {
       right++;
     }
   }
   // Return the value of cnt
   return cnt;
}
int main() {
   string alpha = "abcdda";
   int K = 4;
   cout << "The number of substrings containing all K characters at least once is " << numberOfSubstrings(alpha, K);
   return 0;
}