The length of the smallest substring containing all vowels

A common problem often encountered in string manipulation tasks is to identify the shortest substring that contains each vowel at least once. This task has applications in various fields such as data analysis, bioinformatics, and natural language processing. The goal is to find the smallest consecutive part of an existing string that contains these five letters (a, e, i, o, u) at least once. The selection process to solve this challenge includes a variety of techniques, such as implementing a sliding window algorithm, using a hashing process, or leveraging regular expressions, among others. Finding a robust solution to this problem often becomes crucial, as many real-life scenarios require reliable text manipulation methods.

method

There are various ways to find the length of the smallest substring containing all vowels.

Method 1. Sliding window method

Method 2. Double pointer method

Method 3. Frequency array method

Method 1: Sliding window method

To quickly determine the size of the shortest substring that contains all vowels in each string, use the sliding window method. This method utilizes two pointers, often called "left" and "right", to produce a sliding window that slides along the string.

grammar

Here is the syntax to find the minimum substring length containing all vowels using the sliding window method -

def find_smallest_substring(string):
   vowels = {'a', 'e', 'i', 'o', 'u'}
   unique_vowels = set()
   start = 0
   end = 0
   min_length = float('inf')
    
   while end < len(string):
      # Expand the window
      if string[end] in vowels:
         unique_vowels.add(string[end])
        
      # Contract the window
      while len(unique_vowels) == len(vowels):
         min_length = min(min_length, end - start + 1)
         if string[start] in vowels:
         unique_vowels.remove(string[start])
         start += 1
        
       end += 1
    
   return min_length

algorithm

Step 1 - Use a sliding window of size n (the length of the string) and move it from left to right.

Step 2 - At each position in the window, make sure the substring consists entirely of vowels. If so, update the minimum length of the substring found so far.

Step 3 - Use a hash table to record the number of repetitions of each vowel in a substring to determine if the substring contains all vowels.

Step 4 - If the substring does not contain all vowels, continue testing by moving the window to the right and repeating the process until all potential substrings have been Test completed.

The Chinese translation of

Example 1

is:

Example 1

To determine whether a given character is a vowel in this implementation, we define a helper function isVowel. To describe the sliding window, we also use two pointers on the left and right.

If the current character is a vowel, we first extend the window by adding it to the window collection inside the while loop. Then verify that the size of the window collection is 5 (i.e., all vowels are present). If so, modify the response and reduce the size of the window by eliminating the leftmost character from the window set until it is less than 5.

The result of the loop returns the length of the smallest substring containing all vowels.

#include <iostream>
#include <unordered_set>
using namespace std;

bool isVowel(char c) {
   return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int smallestSubstring(string s) {
   unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
   unordered_set<char> window;
   int n = s.length(), left = 0, right = 0, ans = n + 1;
    
   while (right < n) {
      // Expand the window by adding the current character
      char c = s[right];
      if (isVowel(c)) {
         window.insert(c);
      } 
      right++;
        
      // close the window by removing the leftmost character
      while (window.size() == 5) {
         ans = min(ans, right - left);
         char d = s[left];
         if (isVowel(d)) {
            window.erase(d);
         }
         left++;
      }
   }
   return ans <= n ? ans : 0;
}

int main() {
   string s = "aeeioubcdfuioaei";
   int len = smallestSubstring(s);
   cout << "Length of smallest substring containing all vowels: " << len << endl;
   return 0;
}

Output

Length of smallest substring containing all vowels: 6

Method 2: Double pointer method

The double pointer method is a popular method for quickly solving various string manipulation problems. The two-pointer technique is very helpful in determining the length of the smallest substring containing all vowels.

grammar

This is the syntax to find the minimum substring length containing all vowels using the double pointer method −

function findSmallestSubstring(str):
   vowels = {'a', 'e', 'i', 'o', 'u'}
   count = 0
   left = 0
   minLength = infinity

   for right in range(length of str):
      if str[right] is a vowel:
         count += 1

       while count is same as the total number of vowels:
         minLength = minimum (minLength, right - left + 1)

         if str[left] is a vowel:
         count -= 1

         left += 1

   return minLength

algorithm

Step 1 - Set the start and end pointers to point to the starting position of the string respectively.

Step 2 - Continue to move the end pointer to the right until you find a substring containing only vowels.

Step 3 − If we find a substring that contains all vowels, move the starting cursor to the right until it no longer contains all vowels.

Step 4 − Continue to move the tail pointer to the right until a new substring is found that contains all vowels, and then move the start pointer to the right until the substring no longer contains All vowels.

Step 5 - Refresh the shortest substring length so far.

The Chinese translation of

Example 2

is:

Example 2

In this example, in order to represent the sliding window, we retain two pointers, left and right. From left to right, we iterate through the string str, each time checking whether the current character is a vowel. To keep track of the vowels observed so far, if it's a vowel, we add it to the set viewed.

We move the left cursor to reduce the length of the substring, once we see that the substring contains all vowels. This process continues until the right cursor reaches the end of the string.

Returns the length of the shortest substring containing all vowels. If no such substring exists, 0 is returned.

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int smallestSubstringLength(const string& str) {
   int n = str.length();
   unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};

   unordered_set<char> seen;
   int left = 0, right = 0;
   int smallestLength = n + 1;

   while (right < n) {
      if (vowels.find(str[right]) != vowels.end()) {
         seen.insert(str[right]);
      }

      if (seen.size() == vowels.size()) {
         while (seen.size() == vowels.size()) {
            if (right - left + 1 < smallestLength) {
               smallestLength = right - left + 1;
            }

            if (vowels.find(str[left]) != vowels.end()) {
               seen.erase(str[left]);
            }

            left++;
         }
      }
      right++;
   }
   return (smallestLength == n + 1) ? 0 : smallestLength;
}

int main() {
   string str = "aeeiiouuobcdaeiou";
   int length = smallestSubstringLength(str);
   cout << "Length of the smallest substring containing all vowels: " << length << endl;
   return 0;
}

Output

Length of the smallest substring containing all vowels: 7

Method 3. Frequency array method

Use the frequency array method to measure the shortest substring containing all vowels in each string. It requires building a frequency array to record the number of occurrences of vowels and then repeatedly iterating over the text to locate the desired substring.

grammar

The syntax for finding the smallest substring containing all vowels is as follows -

# Check if all vowels are present in the current substring
if all(freq[vowel] > 0 for vowel in vowels):
   # Update the minimum length if needed
   min_length = min(min_length, right - left + 1)
    
   # Move the left pointer to find a potentially smaller substring
   while left < right:
      freq[input_string[left]] -= 1
      if freq[input_string[left]] == 0:
      break
      left += 1

# Move the right pointer to expand the current substring
right += 1

算法

步骤 1 − 为了记录每个元音字母（a，e，i，o，u）的重复次数，从大小为5的频率数组开始。

第二步 - 创建开始和结束指针，分别标记字符串的开头。

第三步 - 继续将结束指针向右移动，直到每个元音字母至少被听到一次。

步骤4 − 将起始指针向右移动，直到子字符串不再包含至少每个元音字母的重复。

第五步 - 调整已经识别出的子字符串的最小长度，然后将结束指针向右移动，直到发现一个包含所有元音字母的新子字符串。

步骤 6 - 在每个位置更新频率数组，以验证当前子字符串是否包含所有元音字母。

Example 3

的中文翻译为：

示例3

在这个例子中，函数min Length Substring接受一个字符串作为输入，并计算包含所有五个元音字母（a，e，i，o，u）的最小子字符串的长度。

该函数使用名为vowelCount的频率数组来计算子字符串中的每个元音字母的数量。它通过维护一个名为distinctVowels的计数器来跟踪子字符串中不同元音字母的数量。

通过使用两个指针，即start和finish，该函数循环遍历字符串，对每个遇到的元音字母增加频率数组的vowelCount。一旦找到了每个不同的元音字母，子字符串就开始从起始位置收缩，直到没有不同的元音字母为止。如果发现了更短的子字符串，则更新最小子字符串的长度。

主要功能使用字符串来展示如何使用最小长度子字符串方法，通过输入包含所有元音字母的最短子字符串的长度。

#include <iostream>
#include <climits>
using namespace std;

int minLengthSubstring(const string& str) {
   const string vowels = "aeiou";
   int vowelCount[5] = {0};  // Frequency array for vowels
   int distinctVowels = 0;  // Count of distinct vowels in the substring

   // Initialize the minimum length to maximum integer value
   int minLength = INT_MAX;

   int start = 0, end = 0;
   while (end < str.length()) {
      // Increment frequency for vowel at 'end' position
      for (int i = 0; i < 5; i++) {
         if (str[end] == vowels[i]) {
            if (vowelCount[i] == 0) {
               distinctVowels++;
            }
            vowelCount[i]++;
            break;
         }
      }

      // If all distinct vowels are found
      if (distinctVowels == 5) {

         while (start < end) {
            // Update minimum length if a shorter substring is found
            if (minLength > end - start + 1) {
               minLength = end - start + 1;
            }

            // Decrement frequency for vowel at 'start' position
               for (int i = 0; i < 5; i++) {
               if (str[start] == vowels[i]) {
                  vowelCount[i]--;
                  if (vowelCount[i] == 0) {
                     distinctVowels--;
                  }
                  break;
               }
            }
            start++;

            // Break if any distinct vowel is missing in the substring
            if (distinctVowels < 5) {
               break;
            }
         }
      }

      end++;
   }

   return minLength == INT_MAX ? -1 : minLength;
}

int main() {
   string str = "aeeioubcdofu";
   int length = minLengthSubstring(str);

   if (length == -1) {
      cout << "No substring containing all vowels found." << endl;
   } else {
      cout << "Length of the smallest substring containing all vowels: " << length << endl;
   }
   return 0;
}

输出

Length of the smallest substring containing all vowels: 6

结论

总之，找到The length of the smallest substring containing all vowels是一个可以使用各种技术高效解决的问题。通过使用滑动窗口方法或散列元音字母的出现次数，可以遍历字符串并识别满足要求的最小子字符串。这些方法的时间复杂度通常是线性的，适用于大规模输入。然而，重要的是处理边界情况并考虑可能影响解决方案的额外约束条件。总的来说，通过正确的算法方法，可以有效地确定The length of the smallest substring containing all vowels。

The above is the detailed content of The length of the smallest substring containing all vowels. For more information, please follow other related articles on the PHP Chinese website!