C++ 具有相等数量小写和大写字母的子字符串数量

在这个问题中，我们需要计算给定字符串中包含相等数量小写和大写字符的所有字符串的总数。解决这个问题的朴素方法是找到所有子字符串，并计算具有相等数量小写和大写字符的子字符串的总数。

高效的方法是使用子数组和问题。我们可以将小写字符视为-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个索引取一个子字符串

• 在嵌套循环中，如果字符是大写的，将’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。此外，我们将使用映射数据结构来存储以前的前缀和的频率。如果我们找到了一个等于零的前缀和或与存储在映射中的任何前缀和相同的前缀和，我们可以增加计数值。

步骤

• 定义包含整数键值对的“sum”映射。

• 定义“cnt”变量并初始化为零，以存储具有相等小写和大写字符的子字符串总数。还定义“current”变量以存储前缀和。

• 开始遍历字符串。如果当前字符是大写，则将1添加到“current”变量中。否则，从“current”字符中减去1。

• 如果“current”的值为0，我们找到了子字符串，并将“cnt”的值增加1。

• 检查映射是否包含“current”作为键。如果是，则获取其值并将其添加到“cnt”变量中。

• 在映射中将“current”键的值增加1。

示例

为了更好地理解该问题，让我们调试输入示例，即“TutOR”。

因此，当我们开始迭代字符串时，第一个索引处的“current”值将变为0。因此，将“cnt”的值增加1。再次，第3个索引处它将变为零。因此，将“cnt”的值增加1，它将变为2。我们之前也得到过0，因此它存在于映射中，我们需要将那个值添加到“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)，因为我们使用映射表存储前缀和。在最坏情况下，当字符串包含全部小写或大写字符时，我们需要O(N)的空间。

我们学到了两种不同的方法来解决上述问题。第一种方法使用嵌套循环检查所有字符串，而第二种方法在时间复杂度上更高效，但占用更多空间。