最長的具有K個不同元音字母的子串

在本文中，我們將探討在給定字串中找到包含K個不同元音字母的最長子字串的問題。可以使用不同的演算法在C 中解決這個問題。這個問題在電腦科學領域中經常遇到，特別是在文字處理和自然語言處理任務中。它考察了一個人操作字串和處理邊界情況的能力。

文法

在C 領域中，類別std::string代表了字串資料類型。這個多功能的實體可以用於儲存和操作字元序列。

模板類別 std::vector 體現了動態數組的特性，允許調整數組大小並對封裝的元素執行一系列操作。

作為一個類別模板​​，std::unordered_map封裝了一個無序映射結構。它允許儲存單一鍵值對，其中鍵保持不匹配，可以使用這些不同的鍵來檢索值。

函數模板std::max傳回兩個值中的最大值。這個多功能機制可以方便地比較任何資料類型，只要>運算子被正確定義。

std::string
std::vector
std::unordered_map
std::max

演算法

• 開始

• 初始化變數以儲存最長子字串及其長度。

• 迭代遍歷字串以找到具有K個不同元音的子字串。

• 比較子字串的長度，並相應地更新最長子字串及其長度。

• 重複步驟2和3，直到所有子字串都被評估。

• 傳回最長的子字串。

• 結束

方法

• 方法1 - 暴力破解

• #方法2 − 滑動視窗

#方法1：暴力破解

此實作體現了一種暴力方法，用於發現具有精確k個唯一元音字母的字串的最長子字串。程式碼透過定義兩個輔助函數來啟動：is_vowel和has_k_distinct_vowels。

Example

的中文翻譯為：

範例

is_vowel函數接收一個單獨的字元作為輸入，並在字元是元音字母（例如'a'，'e'，'i'，'o'或'u'）時傳回真值，否則傳回假值。這個函數後來被用來確認一個字元是否是元音字母。

has_k_distinct_vowels函數接受一個字串和一個整數k作為輸入，並傳回一個真值，如果字串剛好包含k個唯一的母音字母，則傳回真值，否則傳回假值。此函數使用unordered_set來記錄字串中的母音字母，並計算字串中唯一母音字母的數量。

主要功能longest_substring_bruteforce接收一個字串和一個整數k作為輸入，並傳回字串中包含精確k個唯一元音字母的最長子字串。

這是透過利用兩個巢狀的for迴圈來遍歷字串的所有可能子字串來實現的。對於每個子字串，它呼叫has_k_distinct_vowels函數來驗證子字串是否恰好有k個唯一的元音字母。

如果當前子字串具有k個唯一的元音字母，並且比當前最長的子字串更廣泛，則當前子字串將變成新的最長子字串。

最後，程式碼輸入一個字串和一個整數k，呼叫longest_substring_bruteforce函數來找出具有k個唯一元音字母的最長子字串，並輸出結果。

#include <iostream>
#include <string>
#include <unordered_set>

bool is_vowel(char c) {
   return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

bool has_k_distinct_vowels(const std::string &s, int k) {
   std::unordered_set<char> vowel_set;
   for (char c : s) {
      if (is_vowel(c)) {
         vowel_set.insert(c);
      }
   }
   return vowel_set.size() == k;
}

std::string longest_substring_bruteforce(const std::string &s, int k) {
   std::string longest_substring = "";
   int max_len = 0;

   for (int i = 0; i < s.size(); ++i) {
      for (int j = i; j < s.size(); ++j) {
         std::string current_substring = s.substr(i, j - i + 1);
         if (has_k_distinct_vowels(current_substring, k) && current_substring.size() > max_len) {
         longest_substring = current_substring;
         max_len = current_substring.size();
         }
      }
   }

   return longest_substring;
}

int main() {
   std::string input = "aeiaaioooaauuaeiu";
   int k = 3;
   std::string result = longest_substring_bruteforce(input, k);
   std::cout << "Longest substring with " << k << " distinct vowels: " << result << std::endl;
   return 0;
}

輸出

Longest substring with 3 distinct vowels: iaaioooaa

方法二：滑動視窗

滑動視窗方法是一種用於解決電腦科學和演算法問題的技術。它用於在給定的輸入中查找滿足特定條件的特定模式，例如子字串或子數組。

在這種方法中，使用兩個指標來建立一個滑動窗口，該窗口透過輸入進行滑動。視窗的大小根據需要進行調整，以確保滿足所需的條件。演算法會追蹤目前視窗的屬性，例如不同元素的數量、元素的總和等。

Example

的中文翻譯為：

範例

is_vowel函數是一個幫助函數，如果給定的字元是元音字母（即a，e，i，o或u），則傳回true。

主要函數longest_substring_slidingwindow接受字串s和整數k作為輸入。它使用兩個指針left和right來創建一個滑動窗口，並遍歷字串。

使用無序映射 freq 來追蹤目前視窗中每個元音字母的頻率。當視窗中元音字母的頻率超過 k 時，將左指針向右移動，直到元音字母的頻率再次等於 k。目前視窗的長度計算為 right - left 1，如果大於迄今為止所見過的最大長度，則更新起始索引和長度。

最後，函數使用字串類別的substr方法傳回具有k個不同元音字母的最長子字串。

#include <iostream>
#include <string>
#include <unordered_map>

bool is_vowel(char c) {
   return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

std::string longest_substring_slidingwindow(const std::string &s, int k) {
   int left = 0, right = 0, max_len = 0, start = 0;
   std::unordered_map<char, int> freq;

   while (right < s.size()) {
      char c = s[right];
      if (is_vowel(c)) {
         freq[c]++;
      }

      while (freq.size() > k) {
         char left_char = s[left];
         if (is_vowel(left_char)) {
            freq[left_char]--;
            if (freq[left_char] == 0) {
               freq.erase(left_char);
            }
         }
         left++;
      }

      if (freq.size() == k && (right - left + 1) > max_len) {
         max_len = right - left + 1;
         start = left;
      }

      right++;
   }

   return s.substr(start, max_len);
}

int main() {
   std::string input = "aeiaaioooaauuaeiu";
   int k = 3;
   std::string result = longest_substring_slidingwindow(input, k);
   std::cout << "Longest substring with " << k << " distinct vowels: " << result << std::endl;
   return 0;
}

输出

Longest substring with 3 distinct vowels: iaaioooaa

结论

在本文中，我们讨论了两种方法来解决在给定字符串中找到包含K个不同元音字母的最长子串的问题。第一种方法是暴力法，而第二种方法是滑动窗口法。暴力法的时间复杂度为O(n^3)，使其成为更适合处理较大输入的解决方案。滑动窗口法由于其较低的时间复杂度，推荐用于解决这个问题。

以上是最長的具有K個不同元音字母的子串的詳細內容。更多資訊請關注PHP中文網其他相關文章！