最长的具有K个不同元音字母的子串

在本文中，我们将探讨在给定字符串中找到包含K个不同元音字母的最长子串的问题。可以使用不同的算法在C++中解决这个问题。这个问题在计算机科学领域中经常遇到，特别是在文本处理和自然语言处理任务中。它考察了一个人操作字符串和处理边界情况的能力。

语法

在C++领域中，类std::string代表了字符串数据类型。这个多功能的实体可以用于存储和操作字符序列。

模板类 std::vector 体现了动态数组的特性，允许调整数组大小并对封装的元素执行一系列操作。

作为一个类模板，std::unordered_map封装了一个无序映射结构。它允许存储单个键值对，其中键保持不匹配，可以使用这些不同的键来检索值。

函数模板std::max返回两个值中的最大值。这个多功能机制可以方便地比较任何数据类型，只要>运算符被正确定义。

std::stringstd::vectorstd::unordered_mapstd::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 #include #include 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 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  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

#include #include #include 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 freq;   while (right  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