包含恰好 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 個母音的子字串數量的問題。