最长的具有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。

Cogram

使用AI帮你做会议笔记，跟踪行动项目

下载

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 < 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 
#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 < 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)，使其成为更适合处理较大输入的解决方案。滑动窗口法由于其较低的时间复杂度，推荐用于解决这个问题。