Número de substrings que tienen el mismo número de letras mayúsculas y minúsculas

Dado que la string S consta de letras minúsculas y mayúsculas, la tarea es encontrar el número de substrings que tienen el mismo número de letras minúsculas y mayúsculas.

Ejemplos:

Entrada: S = “gEEk”
Salida: 3
Explicación:
Las siguientes son las substrings que tienen igual número de letras minúsculas y mayúsculas:

1. “gE”
2. «adicto»
3. «Ek»

Por lo tanto, el recuento total de substrings es 3.

Entrada: S = “DÍA DE LA MUJER”
Salida: 4

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las substrings posibles de la string S dada e incrementar el recuento de una substring en 1 si esa substring contiene la misma cantidad de letras minúsculas y mayúsculas. Después de verificar todas las substrings, imprima el valor de la cuenta como resultado. 

Complejidad de Tiempo: O(N ³ )
Espacio Auxiliar: O(1)

Enfoque eficiente: el problema dado se puede resolver considerando cada letra minúscula y mayúscula como 1 y -1 respectivamente, y luego encontrar el recuento de subarreglo que tiene suma 0 . Siga los pasos para resolver el problema:

• Inicialice un HashMap , digamos M que almacena la frecuencia de la suma de todos los prefijos.
• Inicialice una variable, digamos, currentSum como 0 y res como 0 que almacene la suma de cada prefijo y el recuento de las substrings resultantes, respectivamente.
• Atraviese la cuerda y realice los siguientes pasos:
  • Si el carácter actual está en mayúsculas, incremente el valor de currentSum en 1 . De lo contrario, disminuya el valor de currentSum en -1 .
  • Si el valor de currentSum es 0 , incremente el valor de res en 1 .
  • Si el valor de currentSum existe en el mapa M , incremente el valor de res por M[currentSum] .
  • Incremente la frecuencia de currentSum en HashMap M en 1 .
• Después de completar los pasos anteriores, imprima el valor de res como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of
// substrings having an equal number
// of uppercase and lowercase characters
int countSubstring(string& S, int N)
{
    // Stores the count of prefixes
    // having sum S considering uppercase
    // and lowercase characters as 1 and -1
    unordered_map<int, int> prevSum;
 
    // Stores the count of substrings
    // having equal number of lowercase
    // and uppercase characters
    int res = 0;
 
    // Stores the sum obtained so far
    int currentSum = 0;
 
    for (int i = 0; i < N; i++) {
 
        // If the character is uppercase
        if (S[i] >= 'A' and S[i] <= 'Z') {
            currentSum++;
        }
 
        // Otherwise
        else
            currentSum--;
 
        // If currsum is o
        if (currentSum == 0)
            res++;
 
        // If the current sum exists in
        // the HashMap prevSum
        if (prevSum.find(currentSum)
            != prevSum.end()) {
 
            // Increment the resultant
            // count by 1
            res += (prevSum[currentSum]);
        }
 
        // Update the frequency of the
        // current sum by 1
        prevSum[currentSum]++;
    }
 
    // Return the resultant count of
    // the subarrays
    return res;
}
 
// Driver Code
int main()
{
    string S = "gEEk";
    cout << countSubstring(S, S.length());
 
    return 0;
}

// Java program for the above approach
import java.util.HashMap;
 
class GFG{
 
// Function to find the count of
// substrings having an equal number
// of uppercase and lowercase characters
static int countSubstring(String S, int N)
{
     
    // Stores the count of prefixes
    // having sum S considering uppercase
    // and lowercase characters as 1 and -1
    HashMap<Integer, Integer> prevSum = new HashMap<>();
 
    // Stores the count of substrings
    // having equal number of lowercase
    // and uppercase characters
    int res = 0;
 
    // Stores the sum obtained so far
    int currentSum = 0;
 
    for(int i = 0; i < N; i++)
    {
         
        // If the character is uppercase
        if (S.charAt(i) >= 'A' && S.charAt(i) <= 'Z')
        {
            currentSum++;
        }
 
        // Otherwise
        else
            currentSum--;
 
        // If currsum is 0
        if (currentSum == 0)
            res++;
 
        // If the current sum exists in
        // the HashMap prevSum
        if (prevSum.containsKey(currentSum))
        {
             
            // Increment the resultant
            // count by 1
            res += prevSum.get(currentSum);
        }
 
        // Update the frequency of the
        // current sum by 1
        prevSum.put(currentSum,
                    prevSum.getOrDefault(currentSum, 0) + 1);
    }
 
    // Return the resultant count of
    // the subarrays
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "gEEk";
    System.out.println(countSubstring(S, S.length()));
}
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
 
# Function to find the count of
# substrings having an equal number
# of uppercase and lowercase characters
def countSubstring(S, N):
     
    # Stores the count of prefixes
    # having sum S considering uppercase
    # and lowercase characters as 1 and -1
    prevSum = {}
 
    # Stores the count of substrings
    # having equal number of lowercase
    # and uppercase characters
    res = 0
 
    # Stores the sum obtained so far
    currentSum = 0
 
    for i in range(N):
         
        # If the character is uppercase
        if (S[i] >= 'A' and S[i] <= 'Z'):
            currentSum += 1
 
        # Otherwise
        else:
            currentSum -= 1
 
        # If currsum is o
        if (currentSum == 0):
            res += 1
 
        # If the current sum exists in
        # the HashMap prevSum
        if (currentSum in prevSum):
             
            # Increment the resultant
            # count by 1
            res += (prevSum[currentSum])
 
        # Update the frequency of the
        # current sum by 1
        if currentSum in prevSum:
            prevSum[currentSum] += 1
        else:
            prevSum[currentSum] = 1
 
    # Return the resultant count of
    # the subarrays
    return res
 
# Driver Code
if __name__ == '__main__':
     
    S = "gEEk"
    print(countSubstring(S, len(S)))
 
# This code is contributed by bgangwar59

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the count of
// substrings having an equal number
// of uppercase and lowercase characters
static int countSubstring(String S, int N)
{
     
    // Stores the count of prefixes
    // having sum S considering uppercase
    // and lowercase characters as 1 and -1
    Dictionary<int,
               int> prevSum = new Dictionary<int,
                                             int>();
 
    // Stores the count of substrings
    // having equal number of lowercase
    // and uppercase characters
    int res = 0;
 
    // Stores the sum obtained so far
    int currentSum = 0;
 
    for(int i = 0; i < N; i++)
    {
         
        // If the character is uppercase
        if (S[i] >= 'A' && S[i] <= 'Z')
        {
            currentSum++;
        }
 
        // Otherwise
        else
            currentSum--;
 
        // If currsum is 0
        if (currentSum == 0)
            res++;
 
        // If the current sum exists in
        // the Dictionary prevSum
        if (prevSum.ContainsKey(currentSum))
        {
             
            // Increment the resultant
            // count by 1
            res += prevSum[currentSum];
            prevSum[currentSum] = prevSum[currentSum] + 1;
        }
        else
            prevSum.Add(currentSum, 1);
    }
 
    // Return the resultant count of
    // the subarrays
    return res;
}
 
// Driver Code
public static void Main(String[] args)
{
    String S = "gEEk";
    Console.WriteLine(countSubstring(S, S.Length));
}
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript program for the above approach
 
// Function to find the count of
// substrings having an equal number
// of uppercase and lowercase characters
function countSubstring(S, N)
{
    // Stores the count of prefixes
    // having sum S considering uppercase
    // and lowercase characters as 1 and -1
    var prevSum = new Map();
 
    // Stores the count of substrings
    // having equal number of lowercase
    // and uppercase characters
    var res = 0;
 
    // Stores the sum obtained so far
    var currentSum = 0;
 
    for (var i = 0; i < N; i++) {
 
        // If the character is uppercase
        if (S[i] >= 'A' && S[i] <= 'Z') {
            currentSum++;
        }
 
        // Otherwise
        else
            currentSum--;
 
        // If currsum is o
        if (currentSum == 0)
            res++;
 
        // If the current sum exists in
        // the HashMap prevSum
        if (prevSum.has(currentSum)) {
 
            // Increment the resultant
            // count by 1
            res += (prevSum.get(currentSum));
        }
 
        // Update the frequency of the
        // current sum by 1
        if(prevSum.has(currentSum))
            prevSum.set(currentSum, prevSum.get(currentSum)+1)
        else
            prevSum.set(currentSum, 1)
    }
 
    // Return the resultant count of
    // the subarrays
    return res;
}
 
// Driver Code
var S = "gEEk";
document.write( countSubstring(S, S.length));
 
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)