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:
- “gE”
- «adicto»
- «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 3 )
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++
// 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
// 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
# 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#
// 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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA