- cpp-unordered_map, frequency-counting, Hash, HashTable, Mathematical, Strings, substring

Number of substrings having an equal number of lowercase and uppercase letters

Number of substrings having an equal number of lowercase and uppercase lettersGiven string S consisting of lowercase and uppercase letters, the task is to find the number of substrings having the equal number of lowercase and uppercase letters.Examples:Input: S = “gEEk”Output: 3Explanation:Following are the substrings having the equal number of lowercase and uppercase letters:“gE”“gEEk”“Ek”Therefore, the total count of substrings is 3.Input: S = “WomensDAY”Output: 4Naive Approach: The simplest approach to solve the given problem is to generate all possible substring of the given string S and increment the count of substring by 1 if the that substring contains equal number of lowercase and uppercase letters. After checking for all the substrings, print the value of count as the result.Time Complexity: O(N3)Auxiliary Space: O(1)Efficient Approach: The given problem can be solved by considering each lowercase and uppercase letters as 1 and -1 respectively and then find the count of subarray having sum 0. Follow the steps to solve the problem:Initialize a HashMap, say M that stores the frequency of sum of all the prefixes.Initialize a variable say, currentSum as 0 and res as 0 that stores the sum of each prefix and count of resultant substring respectively.Traverse the string and perform the following steps:If the current character is uppercase, then increment the value of currentSum by 1. Otherwise, decrement the value of currentSum by -1.If the value of currentSum is 0, then increment the value of res by 1.If the value of currentSum exists in the map M, then increment the value of res by M[currentSum].Increment the frequency of currentSum in the HashMap M by 1.After completing the above steps, print the value of res as the result.Below is the implementation of the above approach:C++  #include using namespace std;  int countSubstring(string& S, int N){                unordered_map prevSum;                  int res = 0;          int currentSum = 0;      for (int i = 0; i < N; i++) {                  if (S[i] >= ‘A’ and S[i]