具有相同數量小寫字母和大寫字母的子字串數量

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

有效的方法是使用子數組求和問題。我們可以將小寫字元視為-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

的中文翻譯為：

範例

#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)，因為我們使用常數空間。

方法二

在這種方法中，我們將最佳化上述方法的程式碼，以改善解決方案的時間複雜度。我們將大寫字元視為 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’為零。

<span style="font-size: 13.125px;">#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;
}</span>

輸出

The total number of substrings that have equal lowercase and uppercase characters is 4

時間複雜度 - O(N)，因為我們只遍歷字串一次。

空間複雜度 – O(N)，因為我們使用映射來儲存前綴和。在最壞的情況下，當字串包含所有小寫或大寫字元時，我們需要 O(N) 空間。

我們學會了使用兩種不同的方法來解決上述問題。第一種方法使用巢狀循環檢查所有字串，而第二種方法在時間複雜度上比第一種更有效率，但佔用更多的空間。

以上是具有相同數量小寫字母和大寫字母的子字串數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！