C++ 至少包含前K个字母的子字符串数量

在这个问题中，我们需要计算至少包含所有K个字符中每个字符至少1次出现的子字符串。

这里，我们将使用两种不同的方法来解决这个问题。第一种方法是获取给定字符串的所有子字符串，检查子字符串是否包含所有K个字符，并计算包含所有K个字符的子字符串数量。

第二种方法使用滑动窗口技术来解决这个问题。

问题陈述 - 我们给定一个包含N个字符的字符串alpha。同时，我们给定K，表示只包含前K个字母字符的字符串。我们需要计算总共包含至少1次所有K个字符的子字符串数量。

示例示例

输入

alpha = "abcdda", K = 4;

输出

4

解释 - 包含所有4个字符的子字符串是’abcd’、’abcdd’、’abcdda’和’bcdda’。

输入

alpha = "abc", K = 5

输出

0

说明 - 给定的字符串中没有包含所有5个字符的子字符串。

输入

alpha = "ccbba"; K = 3;

输出

2

解释 - 字符串’ccbba’和’cbba’包含所有3个字符。

方法1

在这个方法中，我们将遍历字符串以获取所有子字符串，并将它们存储在列表中。之后，我们将从字符串列表中计算至少包含所有K个字符一次的字符串的数量。

算法

步骤1 - 初始化’subStr’列表以存储所有子字符串。

步骤2 - 开始遍历字符串。同时，使用嵌套循环从1到字符串大小-p进行迭代。

步骤3 - 使用substr()方法从第p个索引开始获取长度为q的子字符串。同时，将子字符串推到’subStr’列表中。

步骤4 - 初始化’result’为0，用于存储有效子字符串的计数。

步骤5 - 开始遍历子字符串列表，并定义’freq’映射以存储当前字符串中字符的频率。同时，将’chars’初始化为0，用于计算字符串中的不同字符数。

步骤6 - 开始遍历当前字符串。如果映射中字符的频率为0，则更新频率，并将’chars’的值加1。

步骤7 - 如果chars的值等于K，则将’result’增加1。

步骤8 - 返回’result’的值。

示例

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

输出

The number of substrings containing all K characters at least once is 4

时间复杂度 – O(NNM)，其中O(N*N)是获取所有子字符串的时间复杂度，O(M)是遍历字符串的时间复杂度。

空间复杂度 – O(N*N)用于存储所有子字符串。

第二种方法

在这种方法中，我们将使用滑动窗口技术来计算至少包含所有K个字符的子字符串的数量。

算法

第一步 - 初始化“freq”映射以存储字符频率，“left”和“right”指针为0，表示滑动窗口指针，“len”为字符串长度，并将“cnt”初始化为0以存储字符串的数量。

第二步 - 迭代直到“right”小于字符串长度为止。

第三步 - 增加映射中“right”索引处的字符的频率。

第四步 - 如果映射的大小等于K，表示我们找到了包含所有K个字符的子字符串。执行以下步骤。

第四步.1 - 迭代直到映射的大小等于K。

第四步.2 - 将“len – right”添加到“cnt”中。

第四步.3 - 从当前窗口中移除左边的字符，在映射中减小它的频率。如果映射中的字符频率为0，则从映射中删除该字符。

第四步.4 - 在嵌套循环中增加“left”指针。

第四步.5 - 在主循环中增加“right”指针。

第五步 - 否则，增加“right”指针的值。

第六步 - 返回“cnt”的值。

例子

让我们通过示例输入来理解滑动窗口技术如何解决该问题。

输入 – ‘abcdaabc’，K = 4

• 第一个窗口将是包含所有4个字符的’abcd’。因此，我们可以说(0, 3)，(0, 4)，(0, 5)，(0, 6)和(0, 7)所有的子字符串至少包含所有K个字符。

• 之后，从1到4的下一个窗口包含所有的字符。所以，(1, 4)，(1,5)，(1, 6)和(1, 7)所有的子字符串至少包含所有的K个字符一次。

• 这样，我们可以计算每个有效窗口的子字符串数量。

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

输出

The number of substrings containing all K characters at least once is 4

时间复杂度 – O(N)，对于滑动窗口。

空间复杂度 – O(K)，用于在映射中存储频率。

程序员还可以使用数组来存储字符的频率，而不是映射，因为我们可以比映射更快地访问数组中的元素。为了更多练习，程序员尝试解决需要计算仅包含所有K个字符的字符串数量的问题。