数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学包含最多 X 个不同元音的长度为 K 的子字符串计数
在这个问题中，我们需要找到长度为 K 的子字符串的总数，这些子字符串最多包含 X 个不同的元音。我们可以通过两种不同的方式解决这个问题。第一种方法是获取所有子字符串，并计算长度为 K 的每个子字符串中不同的元音数量。第二种方法是使用 map 数据结构并跟踪特定子字符串中不同元音的数量。
问题陈述– 我们给定长度为 N 的字符串 str。该字符串仅包含字母字符。此外，我们还给定 K 和 X 两个正整数。我们需要找到长度为 K 的不同子字符串的总数，这些子字符串最多包含 X 个不同的元音。
示例
输入– str = ‘point’，K = 3，X = 2
输出– 3
解释– 长度为 3 且最多包含 2 个不同元音的子字符串为：
字符串 ‘poi’ 包含 2 个元音。
字符串 ‘oin’ 包含 2 个元音。
字符串 ‘int’ 包含 1 个元音。
输入– str = ‘sdfgh’，K = 3，X = 2
输出– 0
解释– 该字符串不包含任何元音，因此输出为零。
输入– str = ‘aeiou’，K = 2，X = 2
输出– 4
解释– 长度为 2 且最多包含 2 个不同元音的子字符串为：‘ae’，‘ei’，‘io’ 和 ‘ou’。
方法 1
在这种方法中，我们将从给定字符串中获取每个长度为 K 的子字符串。之后，我们将检查子字符串中不同元音的数量，并根据子字符串包含的元音总数返回结果值。
算法
初始化 ‘cnt’ 和 ‘len’ 变量。
开始遍历字符串，从第 0 个索引遍历到 len – k 索引。
使用 substr() 方法获取从索引 i 开始长度为 K 的子字符串。
使用 countDistVowels() 函数计算子字符串中不同的元音数量。
在 countDistVowels() 函数中，使用 map 存储特定元音的存在。
从 map 中访问 a、e、i、o 和 u 键的值，并返回它们的和。
如果子字符串中不同元音的总数小于 K，则将 ‘cnt’ 值加 1。
当循环的所有迭代完成后，返回 ‘cnt’ 值。
示例
#include <bits/stdc++.h>
using namespace std;
int countDistVowels(string str){
int dist = 0;
int len = str.length();
// map to store the presence of vowels
unordered_map<char, int> mp;
// insert vowels in the map
for (int i = 0; i < len; i++){
mp[str[i]] = 1;
}
// return the count of distinct vowels in a string
return mp['a'] + mp['e'] + mp['i'] + mp['o'] + mp['u'];
}
int countSubStr(string str, int K, int X){
// to store the total substring following the given condition
int cnt = 0;
int len = str.size();
for (int i = 0; i <= len - K; i++){
// get a substring of length K
string s = str.substr(i, K);
// If contDistVowels() function returns value less than X, increment cnt by 1.
if (countDistVowels(s) <= X){
cnt++;
}
}
return cnt;
}
int main(void){
string str = "point";
int K = 3, X = 2;
cout << "The number of a substring of length K containing at most X distinct vowels are " << countSubStr(str, K, X);
return 0;
}
输出
The number of a substring of length K containing at most X distinct vowels are 3
时间复杂度 – O(N*K)，因为我们在每个子字符串中计算不同的元音。
空间复杂度 – O(K)，因为我们存储长度为 K 的子字符串。
方法 2
此方法使用滑动窗口技术来解决问题。我们可以计算第一个窗口中不同元音的总数，然后，当我们更新窗口中的字符时，我们继续更新不同元音的数量。
算法
定义 ‘vow’ 变量并初始化为零。另外，定义 map 来存储元音频率。
将字符串转换为小写。
计算从索引 0 开始的长度为 K 的第一个子字符串中不同元音的总数。
如果 ‘vow’ 的值小于或等于 X，则将 ‘cnt’ 值初始化为 1。否则为 0。
从第 1 个索引遍历到 len – k 索引。
如果第 (I – 1) 个字符是元音，则将 ‘vow’ 的值减 1，并在 map 中更新其频率。
我们需要将第 (I – 1 + K) 个字符插入到当前窗口中。如果它是元音，并且它在 map 中的频率为零，则将 ‘vow’ 加 1，并在 map 中更新频率，因为它是在当前窗口中不同的元音。
如果 ‘vow’ 的值小于 X，则将 ‘cnt’ 加 1。
返回 ‘cnt’ 值加 1。
示例
#include <bits/stdc++.h>
using namespace std;
// to check given character is vowel or not
bool isVowel(char ch) {
return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
// function to count the number of substrings of length k containing at most k vowels
int countSubStr(string alpha, int K, int X) {
// to store the count of vowels
int vow = 0;
// creating an unordered map to store the count of vowels
unordered_map<char, int> mp;
// convert string to lowercase
transform(alpha.begin(), alpha.end(), alpha.begin(), ::tolower);
// store total distinct vowels in the string of length k
for (int i = 0; i < K; i++) {
if (isVowel(alpha[i]) && mp[alpha[i]] == 0) {
vow++;
mp[alpha[i]]++;
}
}
// If first substring contains at most x vowels, then increment cnt by 1
int cnt = vow <= X ? 1 : 0;
for (int i = 1; i <= alpha.length() -K; i++) {
// remove i-1th character from the current window
if (isVowel(alpha[i - 1])) {
vow--;
mp[alpha[i - 1]]--;
}
// Insert (i - 1 + K)th character
if (isVowel(alpha[i - 1 + K]) && mp[alpha[i - 1 + K]] == 0) {
vow++;
mp[alpha[i - 1 + K]]++;
}
if (vow <= X)
cnt++;
}
return cnt;
}
int main(void) {
string str = "point";
int K = 3, X = 2;
cout << "The number of a substring of length K containing at most X distinct vowels are " << countSubStr(str, K, X);
return 0;
}
输出
The number of a substring of length K containing at most X distinct vowels are 3
时间复杂度 – O(N)，因为我们遍历字符串。
空间复杂度 – O(1)，因为我们使用常量空间。
我们使用两种方法解决了这个问题。第二种方法使用滑动窗口技术来优化代码。程序员可以尝试计算包含最多 X 个不同元音的任意长度的子字符串的总数，并通过此类问题进行更多练习。
128 次浏览
