Le nombre de sous-chaînes de longueur K contenant exactement X voyelles

Dans ce problème, nous devons trouver le nombre total de sous-chaînes de longueur K qui contiennent exactement K voyelles. Nous verrons deux manières différentes de résoudre le problème. Nous pouvons utiliser une méthode simple pour vérifier le nombre de voyelles dans chaque sous-chaîne de longueur K. De plus, nous pouvons utiliser une approche de fenêtre glissante pour résoudre ce problème.

Énoncé du problème - On nous donne une chaîne str de longueur N, contenant des caractères alphabétiques minuscules et majuscules. Nous devons compter le nombre total de sous-chaînes de longueur K qui contiennent exactement X voyelles.

Exemple

Entrée– str = "TutorialsPoint", K = 3, X = 2

Sortie– 6

Explication– Les sous-chaînes de longueur 3 contenant exactement 2 voyelles sont : 'uto', 'ori', 'ria', 'ial', 'Poi' et 'oin'. p>

Entrée– str = 'aeiou', K = 2, X = 2

Sortie– 4

Explication- Les sous-chaînes de longueur 2 et contenant exactement 2 voyelles sont : 'ae', 'ei', 'io' et 'ou'.

Entrée– str = 'fghjsdfdffg', K = 5, X = 1

Sortie– 0

Explication- La chaîne str ne contient aucune voyelle, nous ne trouvons donc aucune sous-chaîne contenant 1 voyelle.

Méthode 1

Dans cette méthode, nous trouverons chaque sous-chaîne de longueur K de str. Après cela, nous compterons le nombre total de voyelles dans une sous-chaîne spécifique et si nous constatons qu'elles sont égales à X, nous pouvons augmenter le nombre de 1.

Algorithme

• Dans la fonction cntSubStr(), initialisez la variable "cnt" à zéro pour stocker le nombre total de sous-chaînes.

• Utilisez une boucle pour parcourir du 0ème index aux indices len - K, où "len" est la longueur de la chaîne.

• Dans la boucle, utilisez la méthode substr() pour obtenir la sous-chaîne de longueur K à partir du i-ième index.

• Exécutez la fonction countVowel() pour compter le nombre total de voyelles dans la sous-chaîne.

• Dans la fonction countVowel(), initialisez la variable "voyelles" à zéro pour stocker le nombre total de voyelles.

• Parcourez la sous-chaîne, le caractère actuel est une voyelle et ajoutez 1 à la valeur de « voyelles ».

• Retour à "voyelle".

• Dans la fonction cntSubStr(), si le nombre total de voyelles dans la sous-chaîne est égal à X, augmentez la valeur de "cnt" de 1.

• Renvoyer la valeur de "cnt".

Exemple

#include <bits/stdc++.h>
using namespace std;

// function to count the total number of vowels in a string
int cntVowels(string alpha) {
   int vows = 0;
   for (int i = 0; i < alpha.length(); i++) {
      if (alpha[i] == 'a' || alpha[i] == 'e' || alpha[i] == 'i' || alpha[i] == 'o' ||
          alpha[i] == 'u' || alpha[i] == 'A' || alpha[i] == 'E' || alpha[i] == 'I' ||
          alpha[i] == 'O' || alpha[i] == 'U')
          vows++;
   }
   return vows;
}
int cntSubstr(string str, int K, int X) {
   int cnt = 0;
   // traverse the string and check for the total number of vowels in each substring of length K
    for (int i = 0; i <= str.length() - K; i++) {
       // get the substring of length K starting from index i
       string sub = str.substr(i, K);
       // check if the total number of vowels in the substring is equal to X, then increment cnt
       if (cntVowels(sub) == X)
          cnt++;
   }
   return cnt;
}
// Driver code
int main(void) {
   string str = "TutorialsPoint";
   int K = 3, X = 2;
   cout << "The total number of substrings of length " << K << " containing " << X << " vowels is " << cntSubstr(str, K, X);
   return 0;
}

Sortie

The total number of substrings of length 3 containing 2 vowels is 6

Complexité temporelle– O(N*K), lorsque nous parcourons str, parcourons les sous-chaînes dans la fonction countVowel().

Complexité spatiale – O(K) puisque nous stockons les sous-chaînes

Méthode 2

Nous utiliserons la technique de la fenêtre coulissante pour résoudre les problèmes de cette approche. Nous supprimerons le premier caractère de la sous-chaîne et ajouterons 1 caractère à la fin. De plus, nous garderons une trace du nombre de voyelles dans la sous-chaîne actuelle, et s'il est égal à X, nous pouvons incrémenter le nombre de 1.

Algorithme

• Définissez la fonction isVowel() pour renvoyer une valeur booléenne selon qu'un caractère spécifique est une voyelle.

• Dans la fonction cntSubStr(), définissez "total_vow" et initialisez-le à zéro pour stocker le total des voyelles dans la fenêtre actuelle.

• À partir du 0ème index, trouvez le nombre total de voyelles dans la sous-chaîne de longueur K, représentant la première fenêtre.

• Initialisez la variable "cnt" à 1 ou 0 selon que la valeur de "vow" est égale à X.

• Commencez à parcourir la chaîne de la position 1 à l'indice len – K.

• Si le caractère (i-1) est une voyelle, décrémentez la valeur de "total_vow" de 1.

• Si le caractère au (i - 1 + K)ème index est une voyelle, augmentez la valeur de "total_vow" de 1.

• Si "total_vow" est égal à X, augmentez "cnt" de 1.

• Renvoyer la valeur de "cnt".

Exemple

#include <bits/stdc++.h>
using namespace std;
bool isVowel(char ch) {
   // convert character to lowercase
   ch = tolower(ch);
   return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
int cntSubstr(string str, int K, int X) {
   // To store total vowels
   int total_vow = 0;
   // Count the number of vowels in the first window
   for (int p = 0; p < K; p++)
       if (isVowel(str[p]))
            total_vow++;
   // to store the total number of substrings of length K containing X vowels
   int cnt = 0;
   // If the first window contains exactly X vowels, initialize cnt as 1
   cnt = total_vow == X ? 1 : 0;
   // traverse the string
   for (int i = 1; i <= str.length() - K; i++) {
      // exclude the (i - 1)th character from the window and update the total_vow
      total_vow = isVowel(str[i - 1]) ? total_vow - 1 : total_vow;
      // Add [i-1+K]th character to the current window and update total_vow
      total_vow = isVowel(str[i - 1 + K]) ? total_vow + 1 : total_vow;
      // If the current window contains exactly X vowels, increment cnt
      if (total_vow == X)
          cnt++;
   }
   return cnt;
}
int main(void) {
   string str = "TutorialsPoint";
   int K = 3, X = 2;
   cout << "The total number of substrings of length " << K << " containing " << X << " vowels is " << cntSubstr(str, K, X);
   return 0;
}

Sortie

The total number of substrings of length 3 containing 2 vowels is 6

Complexité temporelle - O(N) puisque nous parcourons la chaîne.

Complexité spatiale - O(1) puisque nous n'utilisons aucun espace supplémentaire.

Nous avons optimisé la deuxième méthode et réduit la complexité temporelle du code. De plus, nous optimisons également la complexité spatiale de la deuxième méthode. Ici, nous trouvons le nombre total de sous-chaînes de longueur K qui contiennent exactement X voyelles, mais le programmeur pourrait essayer de trouver le nombre total de sous-chaînes de n'importe quelle longueur contenant exactement K voyelles.

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!