包含所有元音字母的最小子字符串的长度

在字符串操作任务中经常遇到的一个常见问题是识别包含每个元音字母至少一次的最短子字符串。这个任务在数据分析、生物信息学和自然语言处理等各个领域都有应用。目标是找出现有字符串中包含这五个字母（a，e，i，o，u）至少一次的最小连续部分。解决这个挑战的选择过程包括多种技术，比如实现滑动窗口算法、使用哈希过程或利用正则表达式等等。找到这个问题的稳健解决方案通常变得至关重要，因为许多现实场景需要可靠的文本操作方法。

方法

有各种方法可以找到包含所有元音字母的最小子字符串的长度。

方法1. 滑动窗口方法

方法2. 双指针方法

方法3. 频率数组方法

方法一：滑动窗口方法

为了快速确定包含每个字符串中的所有元音字母的最短子字符串的大小，请使用滑动窗口方法。该方法利用两个指针，通常称为“left”和“right”，产生一个滑动窗口，沿着字符串滑动。

语法

这里是使用滑动窗口方法找到包含所有元音字母的最小子字符串长度的语法 -

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

算法

步骤 1 - 使用一个大小为 n（字符串的长度）的滑动窗口，并从左到右移动它。

步骤 2 - 在窗口的每个位置，确保子字符串完全由元音字母组成。如果是，则更新迄今为止发现的子字符串的最小长度。

步骤 3 - 使用哈希表来记录子字符串中每个元音字母的重复次数，以确定子字符串是否包含所有元音字母。

第四步 - 如果子字符串不包含所有的元音字母，则通过将窗口向右移动并重复该过程，继续进行测试，直到所有潜在的子字符串都被测试完。

Example 1

的中文翻译为：

示例1

要确定在这个实现中给定的字符是否是元音字母，我们定义了辅助函数 isVowel。为了描述滑动窗口，我们还利用了左右两个指针。

如果当前字符是元音字母，我们首先通过将其添加到while循环内的窗口集合来扩展窗口。然后验证窗口集合的大小是否为5（即，所有元音字母都存在）。如果是，则修改响应并通过从窗口集合中消除最左边的字符来减小窗口的大小，直到小于5。

循环的结果返回包含所有元音字母的最小子字符串的长度。

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

输出

Length of smallest substring containing all vowels: 6

方法2：双指针法

双指针方法是一种受欢迎的快速解决各种字符串操作问题的方法。双指针技术在确定包含所有元音字母的最小子字符串的长度方面非常有帮助。

语法

这是使用双指针方法找到包含所有元音字母的最小子字符串长度的语法−

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

算法

第一步 - 设置起始和结束指针，分别指向字符串的起始位置。

第二步 - 继续将结束指针向右移动，直到发现一个只包含元音字母的子字符串。

步骤 3 − 如果我们找到一个包含所有元音字母的子字符串，则将起始光标向右移动，直到不再包含所有元音字母。

步骤 4 − 继续将尾指针向右移动，直到发现一个包含所有元音字母的新子字符串，然后将起始指针向右移动，直到子字符串不再包含所有元音字母。

第五步 - 刷新到目前为止的最短子字符串长度。

Example 2

的中文翻译为：

示例2

在这个例子中，为了表示滑动窗口，我们保留了两个指针，left和right。从左到右，我们遍历字符串str，每次检查当前字符是否是元音字母。为了保持追踪到目前为止观察到的元音字母，如果是元音字母，我们将其添加到集合viewed中。

我们将左游标移动以减少子字符串的长度，一旦看到的子字符串包含了所有的元音字母。这个过程会一直进行，直到右游标到达字符串的末尾。

返回包含所有元音字母的最短子字符串的长度。如果不存在这样的子字符串，则返回0。

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

输出

Length of the smallest substring containing all vowels: 7

方法3. 频率数组方法

使用频率数组方法来测量每个字符串中包含所有元音字母的最短子字符串。它需要构建一个频率数组来记录元音字母的出现次数，然后通过重复迭代文本来定位所需的子字符串。

语法

找到包含所有元音字母的最小子字符串的语法如下 -

# 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

结论

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

以上是包含所有元音字母的最小子字符串的长度的详细内容。更多信息请关注PHP中文网其他相关文章！