包含等量大小写字母的子字符串的数量
在这个问题中，我们需要计算给定字符串中大小写字母数量相等的字符串的总数。解决这个问题的简单方法是找出所有子字符串，并计算大小写字母数量相等的子字符串的总数。
高效的方法是使用子数组求和问题。我们可以将小写字母视为 -1，将大写字母视为 +1，我们将学习这两种方法来解决这个问题。
问题描述- 我们给定一个包含小写和大写字母的字符串 str。我们需要计算包含等量大小写字符的子字符串的总数。
示例
输入 – str = 'TutOR'
输出 – 4
解释 – 我们可以得到 'Tu'、'TutO'、'tO' 和 'utOR' 共 4 个包含等量大小写字符的子字符串。
输入 – str = 'abcd'
输出 – 0
解释 – 由于字符串仅包含小写字母，因此我们无法得到任何包含等量大小写字符的子字符串。字符
输入 – str = 'XYz'
输出 – 1
解释 – 我们只能得到'Yz'子字符串。
方法 1
这是解决问题的简单方法。我们将使用 3 个嵌套循环来查找给定字符串的所有子字符串。我们将检查每个子字符串是否包含相同数量的小写和大写字符。如果是，我们将计数值加 1。
算法
定义"cnt"变量并将其初始化为零。
使用 for 循环遍历字符串
在循环中，定义"upperCase"和"lowerCase"变量并将其初始化为零
添加另一个嵌套循环，从第 i 个索引开始迭代字符串。因此，我们可以从第 i 个索引到第 j 个索引处取一个子字符串。
在嵌套循环中，如果字符是大写，则将大写字母的值加 1。否则，将小写字母变量的值加 1。
如果'upperCase'和'lowerCase'变量的值相等，则将'cnt'的值加 1。
返回'cnt'的值。
示例
#include <iostream>
using namespace std;
// 函数用于查找大小写字符数量相等的子字符串的总数
int totalSubStrings(string &str, int N){
// 用于存储计数的变量。
int cnt = 0;
for (int i = 0; i < str.length(); i++){
// 用于存储大写和小写字符数量的变量
int upperCase = 0;
int lowerCase = 0;
for (int j = i; j < str.length(); j++){
// 如果字符是大写，则增加 upperCase
if (str[j] >= 'A' && str[j] <= 'Z')
upperCase++;
else
lowerCase++;
// 如果大写字母和小写字母的数量相等，则增加cnt
if (upperCase == lowerCase)
cnt++;
}
}
return cnt;
}
int main(){
string str = "TutOR";
cout << "具有相同小写和大写字符的子字符串总数为 " << totalSubStrings(str, str.length());
return 0;
}
输出
具有相同小写和大写字符的子字符串总数为 4
时间复杂度 – O(N^2)，因为我们使用嵌套循环来查找所有子字符串。
空间复杂度 – O(1)，因为我们使用常数空间。
方法 2
在此方法中，我们将优化上述方法的代码，以提高解决方案的时间复杂度。我们将大写字母视为 +1，小写字母视为 -1。此外，我们将使用 map 数据结构来存储先前前缀和的频率。如果我们发现前缀和等于零或与 map 中存储的任何前缀和相同，则可以增加计数值。
算法
定义包含整数作为键对值的 'sum' map。
定义 'cnt' 变量并将其初始化为零，以存储大小写字符相等的子字符串。另外，定义"current"变量来存储前缀和。
开始遍历字符串。如果当前字符是大写，则将"current"变量加 1。否则，将"current"字符减 1。
如果"current"的值为 0，则表示我们找到了子字符串，并将"cnt"的值加 1。
检查 map 是否包含"current"作为键。如果是，则获取其值并将其添加到"cnt"变量中。
在 map 中将"current"键的值加 1。
示例
为了更好地理解问题，我们来调试示例输入"TutOR"。
因此，当我们开始迭代字符串时，在第一个索引处，"current"值将变为 0。因此，将"cnt"的值加 1。同样，在第三个索引处，它将为零。因此，将"cnt"值加 1，变为 2。我们之前得到的也是 0，所以它存在于映射中，我们需要将该值添加到"cnt"中。因此，它将变为 3。
当我们到达第 4 个索引时，"current"变量的值将为 1，我们再次获得它，就像我们在第 0 个索引处获得它一样。因此，将"cnt"加 1。
基本逻辑是，如果"current"为 0，我们将获得子字符串。如果我们再次获得"current"值，我们可以将两个索引之间的字符串作为"current - current"的零。
#include <iostream>
#include <unordered_map>
using namespace std;
// 函数用于查找大小写字符数量相等的子字符串的总数
int totalSubStrings(string &str, int N){
// 映射用于存储大小写字符数量差异所产生的和的频率
unordered_map<int, int> sum;
// 存储大小写字符数量相等的子字符串的数量
int cnt = 0;
// 当前和
int current = 0;
for (int i = 0; i < N; i++){
// 如果字符为大写，则增加当前值
if (str[i] >= 'A' and str[i] <= 'Z'){
current++;
}
// 否则，减少当前值
else
current--;
// 如果当前值为 0，则表示找到了子字符串。因此，将计数加 1
if (current == 0)
cnt++;
// 如果当前值存在于 map 中，则通过添加当前值的频率来更新 cnt
if (sum[current]){
cnt += (sum[current]);
}
// 增加 map 中当前值的频率
sum[current]++;
}
return cnt;
}
int main(){
string str = "TutOR";
cout << "具有相同小写和大写字符的子字符串总数为 " << totalSubStrings(str, str.length());
return 0;
}
输出
具有相同小写和大写字符的子字符串总数为 4
时间复杂度 – O(N)，因为我们遍历了字符串一次。
空间复杂度 – O(N)，因为我们使用映射来存储前缀和。在最坏的情况下，当字符串包含所有小写或大写字符时，我们需要 O(N) 的空间。
我们学习了使用两种不同的方法来解决上述问题。第一种方法使用嵌套循环检查所有字符串，第二种方法在时间复杂度上比第一种方法更高效，但空间消耗更大。
