包含恰好 K 个不同元音的子字符串的数量
在这个问题中,我们需要计算字符串 str 中恰好包含 K 个不同元音的子字符串的总数。我们可以通过两种不同的方式解决这个问题。第一种方法是遍历所有子字符串并计算每个子字符串中的元音数量。我们还可以使用 map 数据结构来优化第一种方法的代码。
问题陈述– 我们给出了长度为 N 的字符串 str。该字符串包含大写和小写字母字符。另外,我们给出了整数 K。我们需要找到 str 中恰好包含 K 个不同元音的子字符串的总数。
注意– 在这里,我们假设"a"和"A"相等。
示例
输入– str = "point",K = 2
输出– 6
解释– 恰好包含 2 个元音的 str 的子字符串为:'poi'、'oin'、'oint'、'poin'、'point' 和 'oi'。
输入– str = 'abcurso',K = 3
输出– 1
解释– str 的子字符串恰好包含 3 个元音,即 str 本身。
输入– str = 'aeiofd', K = 5
输出– 0
解释– 由于字符串仅包含 4 个元音,因此我们需要一个包含 5 个元音的子字符串。因此,不可能找到任何子字符串。
方法 1
在此方法中,我们将获得长度为 1 到 N 的子字符串。我们将检查每个子字符串中的元音总数。如果我们发现任何子字符串恰好包含 K 个元音,我们将计数值增加 1。
算法
定义"cnt"变量以根据给定条件存储子字符串的数量,并定义"len"以存储字符串的长度。
使用两个嵌套循环覆盖 str 的所有子字符串。
从第 i 个索引开始获取子字符串,其长度为 (q – p + 1)。
使用 cntDistVowel() 函数计算子字符串中的不同元音。
在 cntDistVowel() 函数中,定义映射。
使用 transform() 将字符串转换为小写方法。
遍历字符串并更新字符串中每个字符的映射值。将值从 0 更新为 1。
从映射中返回"a"、"e"、"I"、"o"、"u"键的值的总和。
在 countKSub() 函数中,如果"dis_vowel"等于 K,则将"cnt"的值增加 1。
返回"cnt"值。
示例
#include <bits/stdc++.h> using namespace std; int cntDistVowel(string sub) { // 创建 unordered_map 来存储子字符串中存在的元音 unordered_map<char, int> mp; // 将 sub 转换为小写 transform(sub.begin(), sub.end(), sub.begin(), ::tolower); // 遍历子字符串 for (int p = 0; p < sub.length(); p++) { mp[sub[p]] = 1; } // 返回不同元音的总数 return mp['a'] + mp['e'] + mp['i'] + mp['o'] + mp['u']; } int countkSubs(string str, int k) { // 存储子字符串的总数 int cnt = 0; int len = str.length(); // 遍历字符串 for (int p = 0; p < len; p++) { for (int q = p; q < len; q++) { // 获取从 p 到 q 的子字符串 string sub = str.substr(p, q - p + 1); // 计算子字符串中的不同元音 int dis_vowel = cntDistVowel(sub); // 如果不同元音的数量等于 k,则将 cnt 增加 1 if (dis_vowel == k) cnt++; } } return cnt; } int main() { string str = "point"; int K = 2; cout << "包含恰好 " << K << " 元音的子字符串数量为 " << countkSubs(str, K) << endl; return 0; }
输出
包含恰好 2 个元音的子字符串数量为 6
时间复杂度 – O(N*N*N)。这里,O(N*N) 用于查找所有子字符串,O(N) 用于计算最大长度为 N 的子字符串中的不同元音。
空间复杂度 – O(N),因为我们使用"sub"变量来存储子字符串。
方法 2
此方法包含上述代码的优化版本。在这里,我们在从第 i 个索引开始遍历子字符串时更新映射中存在的字符。当我们找到任何包含恰好 K 个元音的子字符串时,我们会更新计数值。
算法
初始化"cnt"和"len"变量。
使用循环遍历字符串 str。
定义"dist_vowel"变量以存储从索引 p 开始的子字符串中的总不同元音。此外,定义 26 个列表以存储子字符串中元音的存在
使用嵌套循环获取 i 和 j 索引子字符串。
使用 tolower() 函数将字符转换为小写并将其存储到"temp"变量中。
– 使用 isVowel() 函数检查当前字符是否为 bowel。如果是,且不在映射中,则将 dist_vowel 的值增加 1。同时,更新映射的值。
如果"disst_vowel"的值等于 K,则增加"cnt"的值。
如果"dist_vowel"的值大于 K,则中断嵌套循环。
返回"cnt"的值。
示例
#include <bits/stdc++.h> using namespace std; bool isVowel(char ch) { return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ); } int countkSubs(string alpha, int k) { int len = alpha.length(); // 初始化计数 int cnt = 0; // 覆盖所有子字符串 for (int p = 0; p < len; p++) { // 存储不同元音的数量 int dist_vowel = 0; // 存储字符的数量 vector<int> map(26, 0); // 获取从 p 到 q 的子字符串 for (int q = p; q < len; q++) { char temp = tolower(alpha[q]); // 如果当前字符是元音并且是新的,则将 dist_vowel 增加 1 if (isVowel(temp) && map[temp - 'a'] == 0) dist_vowel++; // 将字符计数增加 1 map[temp - 'a']++; // 如果不同元音的数量为 k,则将计数增加 1 if (dist_vowel == k) cnt++; // 如果不同元音的数量超过 k,则中断 if (dist_vowel > k) break; } } return cnt; } int main() { string alpha = "point"; int K = 2; cout << "包含恰好 " << K << " 元音的子字符串数量为 " << countkSubs(alpha, K) << endl; return 0; }
输出
包含恰好 2 个元音的子字符串数量为 6
时间复杂度 – O(N*N),因为我们使用嵌套循环。
空间复杂度 – O(26) ~ O(1),因为我们用于存储子字符串中元音的存在。
我们学习了两种解决问题的方法。第一种方法是朴素方法,第二种方法是优化方法。在这里,我们解决了计算包含恰好 K 个不同元音的子字符串数量的问题。程序员可以解决计算包含恰好 K 个元音的子字符串数量的问题。