« back

Count the substrings

Tags : geeksforgeeks, string, cpp, easy

Problem Statement - link #

Given a string S. The task is to count the number of substrings which contains equal number of lowercase and uppercase letters.

Your Task:

The task is to complete the function countSubstring() which takes the string S as input parameter and returns the number of substrings which contains equal number of uppercase and lowercase letters.

Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(1)

Examples #

Example 1:

Input:
S = "gEEk"
Output: 3
Explanation: There are 3 substrings of
the given string which satisfy the
condition. They are "gE", "gEEk" and "Ek".

Example 2:

Input:
S = "WomensDAY"
Output: 4
Explanation: There are 4 substrings of 
the given string which satisfy the
condition. They are "Wo", "ensDAY", 
"nsDA" and "sD"

Constraints #

Solutions #


class Solution{
    public:
    int countSubstring(string str) {
        // code here
        unordered_map<int, int> map;
        map[0] = 1;
        int res = 0, sum = 0;
        for(char c: str) {
            sum += (isupper(c) ? 1 : -1);
            if(map.find(sum) != map.end()) {
                res += map[sum];
            }
            map[sum]++;
        }
        return res;
    }
};