GFG Count the Substrings Java Solution

Problem

Problem_Link

Solution Approach

• Condition: Substrings with an equal number of uppercase and lowercase letters
• If the difference between the uppercase and lowercase letters at the starting and ending positions of a specific substring is the same, then that substring satisfies the condition.

Example: “AbaBBa”

• The total number of substrings for the given example is 21, and the number of substrings that meet the condition is 7.
• To calculate the uppercase-lowercase difference, we use +1 for uppercase and -1 for lowercase letters.
• The starting point has no uppercase-lowercase difference, so it is 0.

Index	None	0	1	2	3	4	5
Element	Start	A	b	a	B	B	a
Uppercase-Lowercase Difference	0	1	0	-1	0	1	0

Substrings with the same uppercase-lowercase difference are considered satisfying the condition.

Substring	Index	Uppercase-Lowercase Difference
Ab	None~2	0
aB	2~4	0
Ba	4~6	0
AbaB	None~4	0
baBB	1~5	0
aBBa	2~6	0
AbaBBa	1~5	1

• The first index is not included, and the last index is included. This is because the starting point is 0, and there is no index for it.

Time Complexity: O(n), Space Complexity: O(n)

import java.util.HashMap;
import java.util.Map;

public class BalancedSubstring {
    public static void main(String[] args) {
        String S = "AbaBBa";
        System.out.println(countSubstring(S));
    }

    public static int countSubstring(String S) {
        int n = S.length();
        int count = 0;
        int diff = 0;
        Map<Integer, Integer> diffMap = new HashMap<>();

        // Initialize diffMap with difference 0
        diffMap.put(0, 1);

        for (int i = 0; i < n; i++) {
            char c = S.charAt(i);

            // Update the uppercase-lowercase difference
            if (Character.isUpperCase(c)) {
                diff++;
            } else if (Character.isLowerCase(c)) {
                diff--;
            }

            // Increase count based on previously encountered difference
            // If the current difference was encountered before, it means there exists a substring with equal counts of uppercase and lowercase letters
            count += diffMap.getOrDefault(diff, 0);

            // Update the current difference and its count in the diffMap
            diffMap.put(diff, diffMap.getOrDefault(diff, 0) + 1);
        }

        return count;
    }
}

Explanation

1. First, initialize a diffMap HashMap. This map is used to store the difference between the counts of uppercase and lowercase letters. Since the initial difference is 0, we add (0, 1) to the map.
2. Use a for loop to iterate through the input string S. The loop runs from index 0 to one less than the length of the string.
3. Retrieve the character c at the current index and determine if it is uppercase or lowercase. If it's uppercase, increment the diff variable by 1; if it's lowercase, decrement diff by 1.
4. If the current difference diff has been encountered before, it means there exists a substring with an equal number of uppercase and lowercase letters. Therefore, add the count of such substrings to the count variable. If the difference hasn't been encountered before, use the getOrDefault method to retrieve 0.
5. Update the diffMap using the current difference diff. If diff already exists in the map, increment its count by 1; if not, add the new difference to the map with a count of 1.
6. After the for loop finishes, return the value stored in count. This value represents the number of substrings that meet the condition of having an equal number of uppercase and lowercase letters.