La sous-chaîne la plus longue avec K voyelles différentes

Dans cet article, nous explorerons le problème de trouver la sous-chaîne la plus longue contenant K voyelles différentes dans une chaîne donnée. Ce problème peut être résolu en C++ en utilisant différents algorithmes. Ce problème est fréquemment rencontré dans le domaine de l'informatique, notamment dans les tâches de traitement de texte et de traitement du langage naturel. Il examine la capacité d'une personne à manipuler des chaînes et à gérer des cas extrêmes.

Grammaire

Dans le champ C++, la classe std::string représente le type de données chaîne. Cette entité polyvalente peut être utilisée pour stocker et manipuler des séquences de caractères.

La classe de modèle std::vector incarne les caractéristiques des tableaux dynamiques, permettant d'ajuster la taille du tableau et d'effectuer une série d'opérations sur les éléments encapsulés.

En tant que modèle de classe, std::unordered_map encapsule une structure de mappage non ordonnée. Il permet de stocker une seule paire clé-valeur où les clés restent incompatibles et les valeurs peuvent être récupérées à l'aide de ces différentes clés.

Le modèle de fonction std::max renvoie le maximum de deux valeurs. Ce mécanisme polyvalent facilite la comparaison de n'importe quel type de données, à condition que l'opérateur >

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

Algorithme

• Démarrer

• Initialisez la variable pour stocker la sous-chaîne la plus longue et sa longueur.

• Parcourez la chaîne pour trouver des sous-chaînes avec K voyelles différentes.

• Comparez la longueur des sous-chaînes et mettez à jour la sous-chaîne la plus longue et sa longueur en conséquence.

• Répétez les étapes 2 et 3 jusqu'à ce que toutes les sous-chaînes aient été évaluées.

• Renvoie la sous-chaîne la plus longue.

• Fin

Méthode

• Méthode 1 - Force Brute

• Méthode 2 − Fenêtre coulissante

Méthode 1 : Fissuration par force brute

Cette implémentation incarne une méthode de force brute pour découvrir la sous-chaîne la plus longue d'une chaîne avec exactement k voyelles uniques. Le code commence par définir deux fonctions d'assistance : is_vowel et has_k_distinct_vowels.

La traduction chinoise de

Exemple

est :

Exemple

La fonction

is_vowel reçoit un seul caractère en entrée et renvoie une valeur vraie si le caractère est une voyelle (comme 'a', 'e', ​​​​​​'i', 'o' ou 'u') et une fausse valeur sinon. Cette fonction a ensuite été utilisée pour déterminer si un caractère était une voyelle.

La fonction

has_k_distinct_vowels accepte une chaîne et un entier k en entrée et renvoie une valeur vraie si la chaîne contient exactement k voyelles uniques, sinon elle renvoie une fausse valeur. Cette fonction utilise unordered_set pour enregistrer les voyelles dans une chaîne et compter le nombre de voyelles uniques dans la chaîne.

La fonction principale longest_substring_bruteforce reçoit une chaîne et un entier k en entrée et renvoie la sous-chaîne la plus longue de la chaîne contenant exactement k voyelles uniques.

Ceci est réalisé en utilisant deux boucles for imbriquées pour parcourir toutes les sous-chaînes possibles de la chaîne. Pour chaque sous-chaîne, il appelle la fonction has_k_distinct_vowels pour vérifier si la sous-chaîne a exactement k voyelles uniques.

Si la sous-chaîne actuelle a k voyelles uniques et est plus large que la sous-chaîne actuelle la plus longue, la sous-chaîne actuelle deviendra la nouvelle sous-chaîne la plus longue.

Enfin, le code saisit une chaîne et un entier k, appelle la fonction longest_substring_bruteforce pour trouver la sous-chaîne la plus longue avec k voyelles uniques et affiche le résultat.

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

Sortie

Longest substring with 3 distinct vowels: iaaioooaa

Méthode 2 : Fenêtre coulissante

La méthode de la fenêtre glissante est une technique utilisée pour résoudre des problèmes informatiques et algorithmiques. Il est utilisé pour rechercher un modèle spécifique, tel qu'une sous-chaîne ou un sous-tableau, qui satisfait certains critères dans une entrée donnée.

Dans cette méthode, deux pointeurs sont utilisés pour créer une fenêtre coulissante qui glisse par saisie. La taille de la fenêtre est ajustée si nécessaire pour garantir que les conditions requises sont remplies. L'algorithme garde une trace des propriétés de la fenêtre actuelle, telles que le nombre d'éléments distincts, la somme des éléments, etc.

La traduction chinoise de

Exemple

est :

Exemple

La fonction

is_vowel est une fonction d'assistance qui renvoie vrai si le caractère donné est une voyelle (c'est-à-dire a, e, i, o ou u).

La fonction principale longest_substring_slidingwindow accepte la chaîne s et l'entier k comme entrée. Il utilise deux pointeurs gauche et droit pour créer une fenêtre coulissante et parcourir la chaîne.

Utilisez la fréquence de carte non ordonnée pour suivre la fréquence de chaque voyelle dans la fenêtre actuelle. Lorsque la fréquence d'une voyelle dans la fenêtre dépasse k, déplacez le pointeur gauche vers la droite jusqu'à ce que la fréquence de la voyelle soit à nouveau égale à k. La longueur de la fenêtre actuelle est calculée comme suit : droite - gauche + 1, et si elle est supérieure à la longueur maximale vue jusqu'à présent, l'index et la longueur de départ sont mis à jour.

Enfin, la fonction renvoie la sous-chaîne la plus longue avec k voyelles différentes en utilisant la méthode substr de la classe String.

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!