C++ 包含最多X个不同的元音的长度为K的子字符串的计数

在这个问题中，我们需要找到长度为K且最多包含X个不同元音的子字符串的总数。我们可以用两种不同的方法来解决这个问题。第一种方法是获取所有子字符串，并计算长度为K的每个子字符串中的不同元音个数。第二种方法是使用映射数据结构，并跟踪特定子字符串中不同元音的个数。

问题描述 - 我们有一个长度为N的字符串str。字符串中只包含字母字符。同时，我们给出了K和X这两个正整数。我们需要找到长度为K且最多包含X个不同元音的不同子字符串的总数。

示例

输入 - str = ‘point’，K = 3，X = 2

输出 - 3

解释 - 长度为3且最多包含2个不同元音的子字符串为 –

• 字符串’poi’包含2个元音。

• 字符串’oin’包含两个元音。

• 字符串’int’包含1个元音。

输入 - str = ‘sdfgh’，K = 3，X = 2

输出 - 0

解释 - 字符串不包含任何元音，所以输出为零。

输入 - str = ‘aeiou’，K = 2，X = 2

输出 - 4

解释 - 长度为2且最多包含2个不同元音的子字符串为：’ae’，’ei’，’io’和’ou’。

方法1

在这种方法中，我们将从给定字符串中获取长度为K的每个子字符串。然后，我们将检查子字符串中不同元音的个数，并根据子字符串包含的总元音数返回结果值。

步骤

• 初始化 ‘cnt’ 和 ‘len’ 变量。

• 开始遍历字符串，并从第0个索引遍历到len – k个索引。

• 使用 substr() 方法从索引i开始获取长度为K的子字符串。

• 使用 countDistVowels() 函数计算子字符串中不同的元音字母数。

  • 在 countDistVowels() 函数中，使用 map 存储特定元音字母的存在。

  • 从 map 中访问键为 a、e、I、o 和 u 的值，并返回它们的总和。

• 如果子字符串中不同的元音字母总数小于K，则将 ‘cnt’ 的值增加1。

• 当循环的所有迭代完成后，返回 ‘cnt’ 的值。

示例

#include <bits/stdc++.h>
using namespace std;
int countDistVowels(string str){
   int dist = 0;
   int len = str.length();
   // map to store the presence of vowels
   unordered_map<char, int> mp;
   // insert vowels in the map
   for (int i = 0; i < len; i++){
      mp[str[i]] = 1;
   }
   // return the count of distinct vowels in a string
   return mp['a'] + mp['e'] + mp['i'] + mp['o'] + mp['u'];
}
int countSubStr(string str, int K, int X){
   // to store the total substring following the given condition
   int cnt = 0;
   int len = str.size();
   for (int i = 0; i <= len - K; i++){
      // get a substring of length K
      string s = str.substr(i, K);
      // If contDistVowels() function returns value less than X, increment cnt by 1.
      if (countDistVowels(s) <= X){
          cnt++;
      }
   }
   return cnt;
}
int main(void){
   string str = "point";
   int K = 3, X = 2;
   cout << "The number of a substring of length K containing at most X distinct vowels are " << countSubStr(str, K, X);
   return 0;
}

输出

The number of a substring of length K containing at most X distinct vowels are 3

时间复杂度- O(N*K)，因为我们在每个子字符串中计算不同的元音字母数

空间复杂度- O(K)，因为我们存储长度为K的子字符串。

方法2

这种方法使用滑动窗口技术来解决问题。我们可以计算第一个窗口中不同元音字母的总数，然后在更新窗口中的字符时，我们不断更新不同元音字母的计数。

步骤

• 定义“vow”变量并初始化为零。同时，定义一个映射来存储元音字母的频率。

• 将字符串转换为小写。

• 计算从索引0开始的长度为K的第一个子字符串中不同元音字母的总数。

• 如果“vow”的值小于或等于X，将“cnt”的值初始化为1。否则为0。

• 从第1到len-k索引遍历字符串。

• 如果(I-1)th字符是元音字母，则将“vow”的值减1，并将其频率在映射中更新。

• 我们需要将(I-1+K)th字符插入当前窗口。如果它是元音字母，并且其在映射中的频率为零，则将“vow”的值增加1，并在映射中更新频率，因为它是当前窗口中的一个不同的元音字母。

• 如果“vow”的值小于X，则通过1增加“cnt”。

• 返回“cnt”的值加1。

示例

#include <bits/stdc++.h>
using namespace std;
// to check given character is vowel or not
bool isVowel(char ch) {
   return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
// function to count the number of substrings of length k containing at most k vowels
int countSubStr(string alpha, int K, int X) {
   // to store the count of vowels 
   int vow = 0;
   // creating an unordered map to store the count of vowels
   unordered_map<char, int> mp;
   // convert string to lowercase
   transform(alpha.begin(), alpha.end(), alpha.begin(), ::tolower);
   //  store total distinct vowels in the string of length k
   for (int i = 0; i < K; i++) {
      if (isVowel(alpha[i]) && mp[alpha[i]] == 0) {
          vow++;
          mp[alpha[i]]++;
      }
   }
   // If first substring contains at most x vowels, then increment cnt by 1
   int cnt = vow <= X ? 1 : 0;
   for (int i = 1; i <= alpha.length() -K; i++) {
      // remove i-1th character from the current window
      if (isVowel(alpha[i - 1])) {
         vow--;
         mp[alpha[i - 1]]--;
      }
      // Insert (i - 1 + K)th character
      if (isVowel(alpha[i - 1 + K]) && mp[alpha[i - 1 + K]] == 0) {
          vow++;
          mp[alpha[i - 1 + K]]++;
      }
      if (vow <= X)
         cnt++;
   }
   return cnt;
}
int main(void) {
   string str = "point";
   int K = 3, X = 2;
   cout << "The number of a substring of length K containing at most X distinct vowels are " << countSubStr(str, K, X);
   return 0;
}

输出

The number of a substring of length K containing at most X distinct vowels are 3

时间复杂度 – 因为我们遍历字符串所以为O(N)。

空间复杂度 – 因为我们使用常数空间所以为O(1)。

我们用两种方法解决了这个问题。第二种方法使用滑动窗口技术来优化代码。程序员可以尝试计算包含最多X个不同元音字母的任意长度的子字符串的总数，并练习这类问题。