Number of substrings with the same number of lowercase and uppercase letters

In this problem, we need to count the total number of strings that contain the same number of lowercase and uppercase characters in a given string. The naive way to solve this problem is to find all substrings and count the total number of substrings with the same number of lowercase and uppercase characters.

An effective method is to use subarray summation problem. We can treat lower case characters as -1 and upper case characters as 1 and we will learn both ways to solve the problem.

Problem Statement- We are given a string str which contains lowercase and uppercase alphabetic characters. We need to count the total number of substrings that contain the same number of lowercase and uppercase characters.

Example

Input – str = ‘TutOR’

Output – 4

Explanation – We can get 4 substrings, which are 'Tu', 'TutO', 'tO' and 'utOR', which contain the same number of lowercase letters and uppercase letters

Input – str = ‘abcd’

Output – 0

Explanation – We cannot get any substring containing the same lowercase and uppercase characters because the string contains only lowercase characters

Input – str = ‘XYz’

Output– 1

Explanation - We can only get the 'Yz' substring.

method 1

This is a naive way to solve the problem. We will use 3 nested loops to find all substrings of a given string. We will check if each substring contains the same number of lowercase and uppercase characters. If so, we increment the count by 1.

algorithm

• Define variable 'cnt' and initialize it to zero.

• Use a for loop to traverse the string

• In the loop, define the 'upperCase' and 'lowerCase' variables and initialize them with zeros

• Add another nested loop to the code to iterate the string starting from the i-th index. In this way, we can get a substring

from the i-th index to the j-th index

• In nested loops, if the character is uppercase, increase the value of the uppercase variable by 1. Otherwise, increase the value of the lowercase variable by 1.

• If the values ​​of the 'upperCase' and 'lowerCase' variables are equal, increase the value of 'cnt' by 1.

• Return the value of 'cnt'.

Example

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;
}

Output

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

Time complexity - O(N^2), because we use nested loops to find all substrings.

Space complexity - O(1), because we use constant space.

Method Two

In this method, we will optimize the code of the above method to improve the time complexity of the solution. We treat uppercase characters as 1 and lowercase characters as -1. Additionally, we will use a map data structure to store the frequency of the prefix sum. If we find that the prefix sum is equal to zero, or the same as any prefix sum stored in the map, we can increment the count value.

algorithm

• Define a "sum" map containing integers as key-value pairs.

• The variable 'cnt' is defined and initialized to zero to store the total number of substrings with equal lowercase and uppercase characters. At the same time, define the variable 'current' to store the prefix and

• Start traversing the string. If the current character is an uppercase letter, increase the 'current' variable by 1. Otherwise, decrement the 'current' character by 1.

• If the value of 'current' is 0, we find the substring and increment the value of 'cnt' by 1

• Check if the map contains "current" as a key. If it is, then get its value and add it to the "cnt" variable.

• Increase the value of the "current" key in the map by 1.

Example

Example

To better understand the problem. Let's debug the example input, which is 'TutOR'.

So, when we start iterating the string, the value of 'current' will become 0 at the first index. So, increase the value of 'cnt' by 1. Again, at the third index it will go to zero. So, increase the value of 'cnt' by 1 to 2. We also got 0 before, so it's present in the map and we need to add that value to 'cnt'. So, it will become 3.

When we reach the 4th index, the value of the 'current' variable will be 1 and we get it again just like we got it at the 0th index. So add '1' to 'cnt'.

The basic logic is that if 'current' is 0, we get the substring. If we get the value of 'current' again, we can get the string between the two indices as 'current - current' is zero.

<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>

Output

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

Time complexity - O(N), because we only traverse the string once.

Space Complexity – O(N) because we use a map to store the prefix sum. In the worst case, when the string contains all lowercase or uppercase characters, we need O(N) space.

We learned to use two different methods to solve the above problem. The first method uses nested loops to check all strings, while the second method is more efficient than the first in terms of time complexity, but takes up more space.

The above is the detailed content of Number of substrings with the same number of lowercase and uppercase letters. For more information, please follow other related articles on the PHP Chinese website!