计算前缀具有素数个不同字符的字符串的偶数索引
在此问题中，我们将在给定的字符串中找到总无效字符。如果到特定偶数索引为止的总不同字符数为素数，则可以说该字符无效。
我们可以使用 map 数据结构在遍历字符串时计算不同字符的总数。此外，我们可以使用字符串来跟踪不同的数字。此外，对于每个字符，我们可以检查其索引是否为偶数以及不同字符是否为素数。
问题陈述 - 我们给出了一个包含 N 个字符的字符串 alpha。我们需要在给定的字符串中找到总无效字符。如果不同字符的总数是 [0, index] 范围内的素数，则该字符无效，其中 0 <= index < N 且索引为偶数。
示例
输入
alpha = "ppqprs"
输出
2
解释
第 2 个索引为偶数，且总不同字符数为 2，即质数。因此，第 2 个索引无效。
第 4 个索引也是偶数，且总不同字符数为 3，即质数。因此，第 4 个索引也是无效的。
输入
alpha = "tttttt";
输出
0
解释
不同字符的总数为 1，因为字符串的所有字符都相同。
输入
alpha = "abcdefgh";
输出
3
解释
在第 2 个索引处，不同字符的总数为 3。
在第 4 个索引处，不同字符的总数为 5。
在第 6 个索引处，不同字符的总数为 7。
方法 1
在此方法中，我们将找到 0 到 10,00,000 范围内的所有素数。之后，我们将使用 map 数据结构来存储不同字符。如果在任何偶数索引处，不同字符的数量为质数，我们将该索引视为无效索引。
算法
步骤 1 - 执行 computePrimeNums() 函数以查找 0 到 10,00,000 范围内的所有质数。
步骤 1.2 - 在 computePrimeNums() 函数中，用 1 初始化"primeNum"数组元素，假设所有数字最初都是质数。
步骤 1.3 - 如果数字不是质数，我们需要将元素从 1 更新为 0。因此，更新第 0 和第 1 个索引处的元素，因为它们不是质数。
步骤 1.4 - 在所有偶数索引处，将 1 替换为 0，因为偶数不是质数。
步骤 1.5 - 接下来，对于每个奇数，我们需要检查它是否是质数。因此，开始遍历奇数。
步骤 1.6 - 使用另一个嵌套循环遍历奇数并替换 p*q 索引处的元素，因为它不是质数。
步骤 2 - 用 0 初始化"diffChars"变量，以存储特定索引之前不同字符的总数。此外，初始化"cnt"以存储无效字符的数量。我们将使用"freq"映射来存储字符的频率。
步骤 3 - 开始迭代字符串，并且映射中字符的频率为 0，将字符添加到映射中，并将"difChars"增加 1。
步骤 4 - 如果 p 可以被 0 整除，并且"diffChars"是质数，则将"cnt"的值增加 1。
步骤 5 - 返回"cnt"值。
示例
#include <bits/stdc++.h>
using namespace std;
// 存储素数的数组
int primeNum[300];
// 计算素数的函数
void computePrimeNums() {
// 用 1 初始化数组
memset(primeNum, 1, sizeof primeNum);
primeNum[0] = primeNum[1] = 0;
// 所有偶数都是非素数
for (int p = 4; p <= 300; p += 2)
primeNum[p] = 0;
// 对于奇数
for (int p = 3; p * p <= 300; p += 2) {
if (primeNum[p]) {
// 处理非素数
for (int q = 3; q * p <= 300; q += 2)
primeNum[p * q] = 0;
}
}
}
int getInvalidChars(int len, string alpha) {
computePrimeNums();
int diffChars = 0;
// 存储最终答案
int cnt = 0;
// 存储字符频率
unordered_map<char, int> freq;
// 遍历字符串
for (int p = 0; p < len; p++) {
// 如果我们第一次得到一个角色
if (freq[alpha[p]] == 0) {
freq[alpha[p]]++;
diffChars++;
}
// 对于偶数索引和 diffChars 是素数
if (((p % 2) == 0) and primeNum[diffChars]) {
cnt++;
}
}
return cnt;
}
int main(){
int len = 6;
string alpha = "ppqprs";
cout << "无效字符数为 " << getInvalidChars(len, alpha) << endl;
return 0;
}
输出
无效字符数为 2
时间复杂度 − O(N + 300)，因为我们遍历字符串并计算 300 范围内的所有素数。
空间复杂度 − O(1)，因为我们使用常量空间来存储素数。
方法 2
在这种方法中，我们将使用字符串来跟踪不同的字符。此外，我们会在需要时检查素数，而不是预先计算素数。
算法
步骤 1 - 用 0 初始化"cnt"，用空字符串初始化"diffChars"。
步骤 2 - 遍历字符串时，使用 find() 方法检查字符串第 p 个索引中的字符是否存在于"diffCHars"字符串中。如果不存在，则将一个字符附加到"diffChars"字符串。
步骤 3 - 如果索引为偶数，并且"diffChars"字符串的长度为素数，则将"cnt"值增加 1。
步骤 3.1 - 在 checkForPrime() 函数中，如果数字小于或等于 1，则返回 false。
步骤 3.2 - 否则，进行迭代，直到 index*index 小于数字值。
步骤 3.3 - 在循环中，如果数字可以被索引值整除，则返回 false。
步骤 3.4 - 最后，返回 true。
步骤 4 -最后返回'cnt'值。
示例
#include <bits/stdc++.h>
using namespace std;
bool checkForPrime(int num) {
if (num <= 1) {
return false;
}
for (int p = 2; p * p <= num; p++) {
if (num % p == 0) {
return false; // 不是质数
}
}
// 数字是质数
return true;
}
int getInvalidChars(int len, string alpha) {
// 存储最终答案
int cnt = 0;
string diffChars = "";
// 遍历字符串
for (int p = 0; p < len; p++) {
// 如果我们第一次得到一个字符
if (diffChars.find(alpha[p]) == string::npos) {
diffChars += alpha[p];
}
// 对于偶数索引且 diffChars 为素数
if (((p % 2) == 0) and checkForPrime(diffChars.length())) {
cnt++;
}
}
return cnt;
}
int main() {
int len = 6;
string alpha = "ppqprs";
cout << "无效字符数为 " << getInvalidChars(len, alpha) << endl;
return 0;
}
输出
无效字符数为 2
时间复杂度 - O(N*D)，其中 N 是字符串长度，D 是给定字符串中的不同字符总数。
空间复杂度 - O(1)，因为我们不使用任何额外空间。
我们学习了两种在给定字符串中查找无效字符的不同方法。当给定一个包含数百万个字符的大字符串时，第一种方法非常快。第二种方法更节省空间，因为它不使用任何动态空间。
