在这个问题中，我们需要计算给定字符串中包含相同数量的小写和大写字符的字符串的总数。解决这个问题的朴素方法是找到所有的子字符串，并计算具有相同数量的小写和大写字符的子字符串的总数。
有效的方法是使用子数组求和问题。我们可以将小写字符视为-1，将大写字符视为+1，我们将学习这两种方法来解决问题。
问题陈述- 我们给定一个字符串str，其中包含小写和大写字母字符。我们需要计算包含相同数量小写字母和大写字母字符的子字符串的总数。
示例
输入 – str = ‘TutOR’
输出 – 4
解释–我们可以得到4个子字符串，它们分别是'Tu'、'TutO'、'tO'和'utOR'，它们包含相同数量的小写字母和大写字母
输入 – str = ‘abcd’
输出 – 0
解释 – 我们无法获得任何包含相同小写和大写字符的子字符串，因为该字符串仅包含小写字符
输入 – str = ‘XYz’
输出– 1
解释——我们只能得到‘Yz’子字符串。
方法 1
这是解决问题的幼稚方法。我们将使用 3 个嵌套循环来查找给定字符串的所有子字符串。我们将检查每个子字符串是否包含相同数量的小写和大写字符。如果是，我们将计数值增加 1。
算法
定义变量‘cnt’并将其初始化为零。
使用for循环遍历字符串
在循环中，定义‘upperCase’和‘lowerCase’变量并用零初始化它们
在代码中添加另一个嵌套循环，从第i个索引开始迭代字符串。这样，我们可以从第i个索引到第j个索引获取一个子字符串
在嵌套循环中，如果字符是大写的，将大写变量的值增加1。否则，将小写变量的值增加1。
如果'upperCase'和'lowerCase'变量的值相等，则将'cnt'的值增加1。
返回‘cnt’的值。
Example
的中文翻译为：示例
#includeusing namespace std; // function to find the total number of substrings that have an equal number of lowercase and uppercase characters int totalSubStrings(string &str, int N){ // variable to store the count. int cnt = 0; for (int i = 0; i < str.length(); i++){ // variable to store the count of upper and lower case characters int upperCase = 0; int lowerCase = 0; for (int j = i; j < str.length(); j++){ // If the character is in uppercase, then increment upperCase if (str[j] >= 'A' && str[j] <= 'Z') upperCase++; else lowerCase++; // If the count of uppercase and lowercase characters is equal, then increment cnt if (upperCase == lowerCase) cnt++; } } return cnt; } int main(){ string str = "TutOR"; cout << "The total number of substrings that have equal lowercase and uppercase characters is " << totalSubStrings(str, str.length()); return 0; }
输出
The total number of substrings that have equal lowercase and uppercase characters is 4
时间复杂度 - O(N^2)，因为我们使用嵌套循环来查找所有子字符串。
空间复杂度 - O(1)，因为我们使用常量空间。
方法二
在这种方法中，我们将优化上述方法的代码，以改善解决方案的时间复杂度。我们将大写字符视为+1，小写字符视为-1。此外，我们将使用map数据结构来存储前缀和的频率。如果我们发现前缀和等于零，或者与存储在map中的任何前缀和相同，我们可以增加计数值。
算法
定义一个包含整数作为键值对的“sum”映射。
定义变量'cnt'并初始化为零，用于存储具有相等小写和大写字符的子字符串的总数。同时，定义变量'current'用于存储前缀和
开始遍历字符串。如果当前字符是大写字母，则将‘current’变量加1。否则，将‘current’字符减1。
如果‘current’的值为0，我们找到子字符串并将‘cnt’的值增加1
检查地图是否包含“current”作为键。如果是，则获取其值并将其添加到“cnt”变量中。
将地图中“当前”键的值增加 1。
Example
的中文翻译为：示例
为了更好地理解问题。让我们调试一下示例输入，即'TutOR'。
所以，当我们开始迭代字符串时，'current'的值将在第一个索引处变为0。所以，将'cnt'的值增加1。再次，在第三个索引处它将变为零。所以，将'cnt'的值增加1，变为2。我们之前也得到了0，所以它存在于映射中，我们需要将该值添加到'cnt'中。所以，它将变为3。
当我们到达第4个索引时，'current'变量的值将为1，并且我们再次获得它，就像我们在第0个索引处获得它一样。因此，将'1'添加到'cnt'中。
基本逻辑是，如果‘current’为0，我们获取子字符串。如果我们再次得到‘current’的值，我们可以将两个索引之间的字符串作为‘current - current’为零。
#include
#include
using namespace std;
// function to find the total number of substrings that have an equal number of lowercase and uppercase characters
int totalSubStrings(string &str, int N){
// map to store the frequency of sums generated by the difference in the count of lowercase and uppercase characters
unordered_map sum;
// to store the count of substrings that have an equal number of lowercase and uppercase characters
int cnt = 0;
// current sum
int current = 0;
for (int i = 0; i < N; i++){
// If the character is uppercase, then increment the current value
if (str[i] >= 'A' and str[i] <= 'Z'){
current++;
}
// Otherwise, decrement the current value
else
current--;
// If the current value is 0, then a substring is found. So, increment the count by 1
if (current == 0)
cnt++;
// If the current value exists in the map, then update the cnt by adding the frequency of the current value
if (sum[current]){
cnt += (sum[current]);
}
// Increment the frequency of the current value in the map
sum[current]++;
}
return cnt;
}
int main(){
string str = "TutOR";
cout << "The total number of substrings that have equal lowercase and uppercase characters is " << totalSubStrings(str, str.length());
return 0;
}
输出
The total number of substrings that have equal lowercase and uppercase characters is 4
时间复杂度 - O(N)，因为我们只遍历字符串一次。
空间复杂度 – O(N)，因为我们使用映射来存储前缀和。在最坏的情况下，当字符串包含所有小写或大写字符时，我们需要 O(N) 空间。
我们学会了使用两种不同的方法解决上述问题。第一种方法使用嵌套循环检查所有字符串，而第二种方法在时间复杂度上比第一种更高效，但占用更多的空间。
