The longest substring with K different vowels

In this article, we will explore the problem of finding the longest substring containing K different vowels in a given string. This problem can be solved in C using different algorithms. This problem is frequently encountered in the field of computer science, especially in text processing and natural language processing tasks. It examines a person's ability to manipulate strings and handle edge cases.

grammar

In the C field, the class std::string represents the string data type. This versatile entity can be used to store and manipulate character sequences.

The template class std::vector embodies the characteristics of dynamic arrays, allowing the array size to be adjusted and a series of operations performed on the encapsulated elements.

As a class template, std::unordered_map encapsulates an unordered mapping structure. It allows storing a single key-value pair where the keys remain mismatched and the values ​​can be retrieved using these different keys.

Function template std::max returns the maximum of two values. This versatile mechanism makes it easy to compare any data type, as long as the > operator is correctly defined.

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

algorithm

• start

• Initialize variables to store the longest substring and its length.

• Iterate through the string to find substrings with K different vowels.

• Compare the lengths of substrings and update the longest substring and its length accordingly.

• Repeat steps 2 and 3 until all substrings have been evaluated.

• Return the longest substring.

• Finish

method

• Method 1 - Brute force cracking

• Method 2 − Sliding window

Method 1: Brute force cracking

This implementation embodies a brute force method for discovering the longest substring of a string with exactly k unique vowels. The code starts by defining two helper functions: is_vowel and has_k_distinct_vowels.

The Chinese translation of

Example

is:

Example

The is_vowel function accepts a single character as input and returns true if the character is a vowel (such as 'a', 'e', ​​'i', 'o' or 'u'), otherwise returns false value. This function was later used to determine whether a character was a vowel.

The has_k_distinct_vowels function accepts a string and an integer k as input and returns a true value if the string contains exactly k unique vowels, otherwise it returns a false value. This function uses unordered_set to record the vowels in a string and count the number of unique vowels in the string.

Main function longest_substring_bruteforce receives a string and an integer k as input and returns the longest substring in the string containing exactly k unique vowels.

This is achieved by utilizing two nested for loops to iterate through all possible substrings of the string. For each substring, it calls the has_k_distinct_vowels function to verify whether the substring has exactly k unique vowels.

If the current substring has k unique vowels and is wider than the current longest substring, the current substring will become the new longest substring.

Finally, the code inputs a string and an integer k, calls the longest_substring_bruteforce function to find the longest substring with k unique vowels, and outputs the result.

#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;
}

Output

Longest substring with 3 distinct vowels: iaaioooaa

Method 2: Sliding window

The sliding window method is a technique used to solve computer science and algorithmic problems. It is used to find a specific pattern, such as a substring or subarray, that satisfies certain criteria in a given input.

In this method, two pointers are used to create a sliding window that slides through the input. The size of the window is adjusted as necessary to ensure that the required conditions are met. The algorithm keeps track of properties of the current window, such as the number of distinct elements, the sum of elements, etc.

The Chinese translation of

Example

is:

Example

The is_vowel function is a helper function that returns true if the given character is a vowel (i.e. a, e, i, o or u).

The main function longest_substring_slidingwindow accepts string s and integer k as input. It uses two pointers left and right to create a sliding window and iterate over the string.

Use the unordered map freq to track the frequency of each vowel in the current window. When the frequency of a vowel in the window exceeds k, move the left pointer to the right until the frequency of the vowel equals k again. The length of the current window is calculated as right - left 1, and if greater than the maximum length seen so far, the starting index and length are updated.

Finally, this function uses the substr method of the string class to return the longest substring with k different vowels.

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

The above is the detailed content of The longest substring with K different vowels. For more information, please follow other related articles on the PHP Chinese website!