包含恰好 K 个不同元音的子字符串的计数

---

在这个问题中，我们需要统计字符串 str 的所有子字符串中，包含恰好 K 个不同元音的子字符串的总数。我们可以用两种不同的方法解决这个问题。第一种方法是遍历所有子字符串，并统计每个子字符串中元音的数量。我们还可以使用 map 数据结构来优化第一种方法的代码。

问题陈述 – 我们给定一个长度为 N 的字符串 str。字符串包含大写和小写字母字符。此外，我们还给定了一个整数 K。我们需要找到 str 的所有子字符串中，包含恰好 K 个不同元音的子字符串的总数。

注意 – 在这里，我们假设 'a' 和 'A' 是相等的。

示例

输入 – str = “point”，K = 2

输出 – 6

解释 – str 的子字符串，包含恰好 2 个元音的子字符串有：'poi'、'oin'、'oint'、'poin'、'point' 和 'oi'。

输入 – str = 'abcurso'，K = 3

输出 – 1

解释 – str 的子字符串，包含恰好 3 个元音的子字符串是 str 本身。

输入 – str = 'aeiofd'，K = 5

输出 – 0

解释 – 由于字符串只包含 4 个元音，我们需要一个包含 5 个元音的子字符串。因此，不可能找到任何子字符串。

方法 1

在这种方法中，我们将获得长度从 1 到 N 的子字符串。我们将检查每个子字符串中元音的总数。如果我们发现任何子字符串恰好包含 K 个元音，我们将把计数值增加 1。

算法

• 定义 'cnt' 变量来存储根据给定条件的子字符串计数，以及 'len' 来存储字符串的长度。

• 使用两个嵌套循环来覆盖 str 的所有子字符串。

• 获取从第 i 个索引开始，长度为 (q – p + 1) 的子字符串。

• 使用 cntDistVowel() 函数来统计子字符串中不同的元音。

• 在 cntDistVowel() 函数中，定义 map。

• 使用 transform() 方法将字符串转换为小写。

• 遍历字符串，并更新字符串中每个字符的 map 值。将值从 0 更新为 1。

• 返回 map 中 'a'、'e'、'I'、'o'、'u' 键的值之和。

• 在 countKSub() 函数中，如果 'dis_vowel' 等于 K，则将 'cnt' 的值增加 1。

• 返回 'cnt' 值。

示例

#include <bits/stdc++.h>
using namespace std;
int cntDistVowel(string sub) {
   // creating unordered_map to store vowels present in substring
   unordered_map<char, int> mp;
   // convert sub to lowercase
   transform(sub.begin(), sub.end(), sub.begin(), ::tolower);
   // traverse the substring
   for (int p = 0; p < sub.length(); p++) {
      mp[sub[p]] = 1;
   }
   // return total number of distinct vowels
   return mp['a'] + mp['e'] + mp['i'] + mp['o'] + mp['u'];
}
int countkSubs(string str, int k) {
   // to store the total number of substrings
   int cnt = 0;
   int len = str.length();
   // traverse the string
   for (int p = 0; p < len; p++) {
      for (int q = p; q < len; q++) {
          // get the substring from p to q
          string sub = str.substr(p, q - p + 1);
          // count distinct vowels in the substring
          int dis_vowel = cntDistVowel(sub);
          // if the number of distinct vowels equals k then increment cnt by 1
          if (dis_vowel == k)
             cnt++;
      }
   }
   return cnt;
}
int main() {
   string str = "point";
   int K = 2;
   cout << "The number of substrings containing exactly " << K << " vowels is " << countkSubs(str, K) << endl;
   return 0;
}

输出

The number of substrings containing exactly 2 vowels is 6

时间复杂度 – O(N*N*N)。这里，O(N*N) 用于查找所有子字符串，O(N) 用于统计最大长度为 N 的子字符串中不同的元音。

空间复杂度 – O(N)，因为我们使用 'sub' 变量来存储子字符串。

方法 2

这种方法包含上述代码的优化版本。在这里，我们在遍历从第 i 个索引开始的子字符串时，更新 map 中存在的字符。当我们找到任何包含恰好 K 个元音的子字符串时，我们更新计数值。

算法

• 初始化 'cnt' 和 'len' 变量。

• 使用循环遍历字符串 str。

• 定义 'dist_vowel' 变量来存储从索引 p 开始的子字符串中不同的元音总数。另外，定义一个长度为 26 的列表来存储子字符串中元音的存在情况

• 使用嵌套循环获取 i 和 j 索引的子字符串。

• 使用 tolower() 函数将字符转换为小写，并将其存储到 'temp' 变量中。

• – 使用 isVowel() 函数检查当前字符是否是元音。如果是，并且不在 map 中，则将 dist_vowel 的值增加 1。另外，更新 map 的值。

• 如果 'disst_vowel' 的值等于 K，则将 'cnt' 的值增加 1。

• 如果 'dist_vowel' 的值大于 K，则中断嵌套循环。

• 返回 'cnt' 的值。

示例

#include <bits/stdc++.h>
using namespace std;
bool isVowel(char ch) {
   return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' );
}
int countkSubs(string alpha, int k) {
   int len = alpha.length();
   // Initialize the count
   int cnt = 0;
   // Cover all substrings
   for (int p = 0; p < len; p++) {
      // To store the count of distinct vowels
      int dist_vowel = 0;
      // to store the count of characters
      vector<int> map(26, 0);
      // get a substring from p to q
      for (int q = p; q < len; q++) {
          char temp = tolower(alpha[q]);
          // If the current character is a vowel and new, increment dist_vowel by 1
          if (isVowel(temp) && map[temp - 'a'] == 0)
              dist_vowel++;
          // Increase the character count by 1
          map[temp - 'a']++;
          // If the number of distinct vowels is k, increment count by 1
          if (dist_vowel == k)
              cnt++;
          // If the number of distinct vowels is more than k, break
          if (dist_vowel > k)
              break;
       }
   }
   return cnt;
}
int main() {
   string alpha = "point";
   int K = 2;
   cout << "The number of substrings containing exactly " << K << " vowels is " << countkSubs(alpha, K) << endl;
   return 0;
}

输出

The number of substrings containing exactly 2 vowels is 6

时间复杂度 – O(N*N)，因为我们使用了嵌套循环。

空间复杂度 – O(26) ~ O(1)，因为我们用来存储子字符串中元音的存在情况。

我们学习了两种解决问题的方法。第一种方法是朴素方法，第二种方法是优化的。在这里，我们解决了统计包含恰好 K 个不同元音的子字符串的问题。程序员可以解决统计包含恰好 K 个元音的子字符串数量的问题。