最多有一个字符的频率为奇数的子字符串的数量
子字符串是字符串的连续字符的子集或序列。
现在，在这个问题中，我们需要找到最多有一个字符的频率为奇数的子字符串的数量。让我们看看我们应该如何解决这个问题。
让我们借助一些例子来理解这个问题。
输入 − s = "ksjssjkk"
输出 − 21
解释 − 由于给定字符串中字符的频率如下所示 −
k -> 3
s -> 3
j -> 2
现在，最多有一个字符出现奇数次的子字符串可以是 −
取每个字符:'k'、's'、'j'、's'、's'、'j'、'k'、'k' = 8
一次取 2 个字母:'ss'、'kk' = 2
一次取 3 个字母:'sjs'、'jss'、'ssj'、'jkk' = 4
一次取 4 个字母:'jssj' = 1
一次取 5 个字母:'sjssj'、'jssjk'、'ssjkk' = 3
一次取 6 个字母:'jssjkk' = 1
一次取 7 个字母:'ksjssjk'、'sjssjkk' = 2
一次取 8 个字母:无字符串
现在，添加我们得到的子字符串数量 (8 + 2 + 4 + 1 + 3 + 1 + 2) = 21
输入 − s = "ab"
输出 − 2
解释 − 我们将得到的 2 个子字符串是:'a'、'b'
问题解释
让我们尝试理解问题并找到其解决方案。我们必须找到字符串中最多有一个字母出现奇数次的子字符串，即，总的来说，最多有一个字母的频率为奇数。
解决方案 1:强力解决方案
方法
这是一种易于理解的方法。我们将简单地运行循环来访问所有子字符串，并继续检查是否只有一个字母的频率为奇数。如果是，我们将在最终输出中包含子字符串。
示例:C++ 代码
#include <bits/stdc++.h>
using namespace std;
// 检查字符串是否有效的函数
bool checkValid(string s){
// 定义字符串的大小
int n = s.size();
// 定义频率向量
int Freq[26] = {0};
// 定义一个名为 oddFreq 的变量来计算总奇数频率
int oddFreq = 0;
// 运行循环来计算每个字符的频率
for (int i = 0; i < n; i++){
Freq[s[i] - 'a']++;
}
// 运行循环来计算奇数频率的数量
for (int i = 0; i < 26; i++){
if (Freq[i] % 2 != 0)
oddFreq++;
}
// 检查任何字符的频率是否为奇数大于 1，则返回 false，否则返回 true
if (oddFreq <= 1) return true;
else return false;
}
// 函数用于计算最多有一个字符出现频率为奇数的子字符串的数量
int Helper(string s){
// 定义字符串的大小
int n = s.size();
// 定义一个以零开头的变量 output
int output = 0;
// 运行一个循环来遍历字符串
for(int i = 0; i < n; i++){
// 在第一个循环内运行另一个循环来获取子字符串
for (int j = i; j < n; j++){
// 获取从 i 到 j 的子字符串
string S = s.substr(i, j - i + 1);
if (checkValid(S)) output++;
}
}
// 返回最终输出
return output;
}
int main(){
// 用户输入字符串
string s = "ksjssjkk" ;
// 调用辅助函数获取最终输出
int output = Helper(s);
// 打印输出
cout << "最多有一个字符的频率为奇数的子字符串的数量为:" << output;
return 0;
}
输出
最多有一个字符的频率为奇数的子字符串的数量为:21
上述代码的复杂度
时间复杂度 − O(n^3);其中 n 是字符串的大小，这里 (n^3) 是辅助函数的时间复杂度，而 checkValid 函数本身需要 (O(n)) 时间来执行。
空间复杂度 − O(1)；我们未在上面的代码中将任何变量存储在某些数据结构中。
解决方案 2 使用位掩码的优化解决方案
位掩码
位掩码是将掩码应用于值以保留、更改或修改给定信息的行为。掩码确定要采用哪些位以及要清除二进制数的哪些位。它可用于掩码值以使用各种按位运算来表示集合的子集。
方法
我们使用位掩码来指示哪些字符使用了奇数次，并使用哈希图来跟踪以前看到的位掩码。每次迭代后，我们将 hashmap[bitmask] 加一，表示我们熟悉这个位掩码。当 output += m[mask] 时，将计算使用偶数个字母的子字符串。而 output+= m[mask^ (1<<j)] 将计算恰好一个字母出现奇数次的子字符串。
示例:C++ 代码
#include <bits/stdc++.h>
using namespace std;
// 函数用于查找最多有一个字符的频率为奇数的子字符串的数量
int Helper(string s){
// 声明一个无序映射，它将告诉我们位掩码的频率是奇数还是偶数，如果该字符出现偶数次则为 0，如果出现奇数次则为 1
unordered_map<int, int> m;
// 启动频率位掩码
m[0] = 1;
// 存储当前位掩码
int mask = 0;
// 将输出初始化为 0
int output = 0;
// 运行循环以开始掩码
for (int i = 0; i < s.size(); ++i){
// 屏蔽当前字符
mask ^= (1 << (s[i] - 'a'));
// 计算所有字母使用次数相等的子字符串
output += m[mask];
for (int j = 0; j < 26; ++j){
// 计算恰好有 1 个使用字符的子字符串
output += m[mask ^ (1 << j)];
}
m[mask]++;
}
// 返回最终输出
return output;
}
int main(){
// 用户输入字符串
string s = "ksjssjkk" ;
// 调用辅助函数获取最终输出
int output = Helper(s);
// 打印输出
cout << "频率最多为一个字符为奇数的子字符串的数量为:" << output;
return 0;
}
输出
频率最多为一个字符为奇数的子字符串的数量为:21
上述代码的复杂度
时间复杂度 − O(n*26); 其中 n 是字符串的大小。对于字符串的每个字符，我们检查总共 26 个字符。
空间复杂度 7minus; O(1);我们仅使用了一个 map 数据结构，它占用 O(26) 空间，相对等于 O(1) 空间复杂度。
结论
在本文中，要找到最多有一个字符的频率为奇数的子字符串的数量。首先，我们将应用简单的方法使用循环获取输出，这是一种易于理解的方法，但该方法的唯一缺点是它将以巨大的时间复杂度执行。但是，我们可以通过使用另一种称为使用哈希图的位掩码的技术轻松推导出代码的时间复杂度。特别是这个问题是应用位掩码技术的一个特殊示例，因为它将时间复杂度从 O(n^3) 推导出 O(n)。在本文中，我们学习了位掩码的用法和概念。
