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

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

问题陈述 - 给定长度为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(NNN)。这里，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中的值。

• 如果’dist_vowel’的值等于K，则增加’cnt’的值。

• 如果’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个元音字母的问题。