Bilangan subrentetan panjang K yang mengandungi vokal X tepat

Dalam masalah ini, kita perlu mencari jumlah bilangan subrentetan panjang K yang mengandungi betul-betul vokal K. Kami akan melihat dua cara berbeza untuk menyelesaikan masalah. Kita boleh menggunakan kaedah mudah untuk menyemak bilangan vokal dalam setiap subrentetan panjang K. Selain itu, kita boleh menggunakan pendekatan tetingkap gelongsor untuk menyelesaikan masalah ini.

Pernyataan Masalah - Kami diberi rentetan rentetan panjang N, mengandungi aksara abjad huruf kecil dan huruf besar. Kita perlu mengira jumlah bilangan subrentetan panjang K yang mengandungi vokal X tepat.

Contoh

Input– str = "TutorialsPoint", K = 3, X = 2

Output– 6

Penjelasan– Substring dengan panjang 3 yang mengandungi tepat 2 vokal ialah: 'uto', 'ori', 'ria', 'ial', 'Poi' dan 'oin'. p>

Input– str = ‘aeiou’, K = 2, X = 2

Output– 4

Penjelasan- Substring dengan panjang 2 dan mengandungi tepat 2 vokal ialah: 'ae', 'ei', 'io' dan 'ou'.

Input– str = ‘fghjsdfdffg’, K = 5, X = 1

Output– 0

Penjelasan- Str rentetan tidak mengandungi sebarang vokal, jadi kami tidak dapat menjumpai sebarang subrentetan yang mengandungi 1 vokal.

Kaedah 1

Dalam kaedah ini, kita akan mendapati setiap subrentetan panjang K bagi str. Selepas itu, kita akan mengira jumlah vokal dalam subrentetan tertentu dan jika kita mendapati ia sama dengan X, kita boleh menambah kiraan sebanyak 1.

Algoritma

• Dalam fungsi cntSubStr(), mulakan pembolehubah "cnt" kepada sifar untuk menyimpan jumlah bilangan subrentetan.

• Gunakan gelung untuk beralih daripada indeks ke-0 kepada indeks len - K, dengan "len" ialah panjang rentetan.

• Dalam gelung, gunakan kaedah substr() untuk mendapatkan subrentetan panjang K bermula daripada indeks ke-i.

• Laksanakan fungsi countVowel() untuk mengira jumlah bilangan vokal dalam subrentetan.

• Dalam fungsi countVowel(), mulakan pembolehubah "vokal" kepada sifar untuk menyimpan jumlah bilangan vokal.

• Lintas subrentetan, aksara semasa ialah vokal, dan tambah 1 pada nilai 'vokal'.

• Kembali ke "vokal".

• Dalam fungsi cntSubStr(), jika jumlah bilangan vokal dalam subrentetan adalah sama dengan X, tambahkan nilai "cnt" sebanyak 1.

• Kembalikan nilai "cnt".

Contoh

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

Output

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

Kerumitan masa– O(N*K), apabila kita mengulangi str, mengulangi subrentetan dalam fungsi countVowel().

Kerumitan ruang – O(K) kerana kami menyimpan subrentetan

Kaedah 2

Kami akan menggunakan teknik tingkap gelongsor untuk menyelesaikan masalah dalam pendekatan ini. Kami akan mengalih keluar aksara pertama daripada subrentetan dan menambah 1 aksara pada penghujungnya. Selain itu, kami akan menjejaki kiraan vokal dalam subrentetan semasa, dan jika ia sama dengan X, kami boleh menambah kiraan sebanyak 1.

Algoritma

• Tentukan fungsi isVowel() untuk mengembalikan nilai Boolean berdasarkan sama ada aksara tertentu ialah vokal.

• Dalam fungsi cntSubStr(), takrifkan "total_vow" dan mulakannya kepada sifar untuk menyimpan jumlah vokal dalam tetingkap semasa.

• Bermula dari indeks ke-0, cari jumlah bilangan vokal dalam subrentetan panjang K, mewakili tetingkap pertama.

• Mulakan pembolehubah "cnt" kepada 1 atau 0 bergantung pada sama ada nilai "nazar" bersamaan dengan X.

• Mula melintasi rentetan dari kedudukan 1 ke len – indeks K.

• Jika aksara (i-1) ialah vokal, kurangkan nilai "total_vow" sebanyak 1.

• Jika aksara pada indeks (i - 1 + K) adalah vokal, tambahkan nilai "total_vow" sebanyak 1.

• Jika "total_vow" sama dengan X, naikkan "cnt" sebanyak 1.

• Kembalikan nilai "cnt".

Contoh

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

Output

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

Kerumitan masa - O(N) sejak kita mengulangi rentetan.

Kerumitan Ruang - O(1) kerana kami tidak menggunakan sebarang ruang tambahan.

Kami mengoptimumkan kaedah kedua dan mengurangkan kerumitan masa kod. Di samping itu, kami juga mengoptimumkan kerumitan ruang kaedah kedua. Di sini kita dapati jumlah bilangan subrentetan panjang K yang mengandungi vokal X tepat, tetapi pengaturcara boleh cuba mencari jumlah bilangan subrentetan bagi sebarang panjang yang mengandungi vokal K tepat.

Atas ialah kandungan terperinci Bilangan subrentetan panjang K yang mengandungi vokal X tepat. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!