包含相同數量的小寫字母和大寫字母的子字串的數量

---

在這個問題中，我們需要統計給定字串中包含相同數量的小寫字母和大寫字母的字串總數。解決該問題的樸素方法是找到所有子字串，並統計包含相同數量的小寫字母和大寫字母的子字串的總數。

有效的方法是使用子陣列和問題。我們可以將小寫字母視為 -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) 空間。

我們學習了使用兩種不同方法來解決上述問題。第一種方法使用巢狀迴圈檢查所有字串，而第二種方法在時間複雜度方面比第一種方法更有效，但更消耗空間。