数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究包含相同数量的小写字母和大写字母的子字符串的数量
在这个问题中，我们需要统计给定字符串中包含相同数量的小写字母和大写字母的字符串总数。解决该问题的朴素方法是找到所有子字符串，并统计包含相同数量的小写字母和大写字母的子字符串的总数。
有效的方法是使用子数组和问题。我们可以将小写字母视为 -1，大写字母视为 +1，我们将学习两种解决该问题的方法。
问题陈述- 我们给定一个包含小写和大写字母的字符串 str。我们需要统计包含相同数量的小写字母和大写字母的子字符串的总数。
示例
输入 – str = ‘TutOR’
输出 – 4
说明–我们可以得到 ‘Tu’, ‘TutO’, ‘tO’ 和 ‘utOR’ 共 4 个子字符串，它们包含相同数量的小写字母和大写字母
输入 – str = ‘abcd’
输出 – 0
说明– 我们无法获得任何包含相同数量的小写字母和大写字母的子字符串，因为该字符串仅包含小写字母
输入 – str = ‘XYz’
输出 – 1
说明– 我们只能得到 ‘Yz’ 子字符串。
方法 1
这是解决该问题的朴素方法。我们将使用 3 个嵌套循环来查找给定字符串的所有子字符串。我们将检查每个子字符串是否包含相同数量的小写字母和大写字母。如果是，我们将 count 的值增加 1。
算法
定义变量 ‘cnt’ 并将其初始化为零。
使用 for 循环遍历字符串
在循环中，定义变量 ‘upperCase’ 和 ‘lowerCase’ 并将其初始化为零
添加另一个嵌套循环以从第 i 个索引开始遍历字符串。因此，我们可以从第 I 个到第 j 个索引获取子字符串
在嵌套循环中，如果字符是大写，则将 upperCase 的值增加 1。否则，将 lowercase 变量的值增加 1。
如果 ‘upperCase’ 和 ‘lowerCase’ 变量的值相等，则将 ‘cnt’ 的值增加 1。
返回 ‘cnt’ 的值。
示例
#include <iostream>
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){
// 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)，因为我们使用常量空间。
方法 2
在这种方法中，我们将优化上述方法的代码以提高解决方案的时间复杂度。我们将大写字母视为 +1，小写字母视为 -1。此外，我们将使用 map 数据结构来存储先前前缀和的频率。如果我们找到一个等于零或与存储在 map 中的任何前缀和相同的前缀和，我们可以增加 count 值。
算法
定义包含整数作为键值对的 ‘sum’ map。
定义变量 ‘cnt’ 并将其初始化为零以存储包含相同数量的小写字母和大写字母的子字符串总数。此外，定义变量 ‘current’ 以存储前缀和
开始遍历字符串。如果当前字符是大写，则将 ‘current’ 变量加 1。否则，从 ‘current’ 字符中减去 1。
如果 ‘current’ 的值为 0，则我们找到了子字符串，并将 ‘cnt’ 的值增加 1
检查 map 中是否包含 ‘current’ 作为键。如果是，获取其值并将其添加到 ‘cnt’ 变量中。
在 map 中将 ‘current’ 键的值增加 1。
示例
为了更好地理解问题。让我们调试示例输入，即 ‘TutOR’。
因此，当我们开始遍历字符串时，‘current’ 的值将在第一个索引处变为 0。因此，将 ‘cnt’ 的值增加 1。同样，它将在第 3 个索引处为零。因此，将 ‘cnt’ 的值增加 1，它将变为 2。我们之前也得到了 0，因此它存在于 map 中，我们需要将其值添加到 ‘cnt’ 中。因此，它将变为 3。
当我们到达第 4 个索引时，‘current’ 变量的值将为 1，我们再次得到它，因为我们在第 0 个索引处得到了它。因此，将 ‘1’ 添加到 ‘cnt’ 中。
基本逻辑是，如果 ‘current’ 为 0，则我们得到子字符串。如果我们再次得到 ‘current’ 值，我们可以将两个索引之间的字符串作为 ‘current – current’ 为零。
#include <iostream>
#include <unordered_map>
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<int, int> 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)，因为我们使用 map 来存储前缀和。在最坏的情况下，当字符串包含所有小写或大写字符时，我们需要 O(N) 空间。
我们学习了使用两种不同方法来解决上述问题。第一种方法使用嵌套循环检查所有字符串，而第二种方法在时间复杂度方面比第一种方法更有效，但更消耗空间。
222 次浏览
