Dada una string S de longitud N , la tarea es encontrar el número de substrings no vacías que tienen un número par de vocales .
Ejemplos:
Entrada: N = 5, S = “abcde”
Salida: 7
Explicación:
Todas las substrings posibles con un número par de vocales son:
Substrings Vocales
{abcde} 2
{b} 0
{bc} 0
{bcd} 0
{c} 0
{cd } 0
{d} 0
Entrada: N=4, S=”geeks”
Salida: 6
Enfoque ingenuo:
el enfoque más simple para resolver el problema es generar todas las substrings posibles de la string dada y, para cada substring, contar el número de vocales y verificar si es par o no. Si se encuentra parejo, aumente el conteo . Finalmente, después de verificar todas las substrings, imprima el valor de count como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement //the above approach #include <bits/stdc++.h> using namespace std; // Utility function to check // if a character is a vowel bool isVowel(char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels void countSubstrings(string s, int n) { // Stores the count of substrings int result = 0; for(int i = 0; i < n; i++) { int count = 0; for(int j = i; j < n; j++) { // If the current character // is a vowel if (isVowel(s[j])) { // Increase count count++; } // If substring contains // even number of vowels if (count % 2 == 0) // Increase the answer result++; } } // Print the final answer cout << result; } // Driver Code int main() { int n = 5; string s = "abcde"; countSubstrings(s, n); return 0; } // This code is contributed by Amit Katiyar
Java
// Java Program to implement // the above approach class GFG { // Utility function to check // if a character is a vowel static boolean isVowel(char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels static void countSubstrings(String s, int n) { // Stores the count of substrings int result = 0; for (int i = 0; i < n; i++) { int count = 0; for (int j = i; j < n; j++) { // If the current character // is a vowel if (isVowel(s.charAt(j))) { // Increase count count++; } // If substring contains // even number of vowels if (count % 2 == 0) // Increase the answer result++; } } // Print the final answer System.out.println(result); } // Driver Code public static void main(String[] args) { int n = 5; String s = "abcde"; countSubstrings(s, n); } }
Python3
# Python3 Program to implement # the above approach # Utility function to check # if a character is a vowel def isVowel(c): if (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'): return True return False # Function to calculate and return the # count of substrings with even number # of vowels def countSubstrings(s, n): # Stores the count of substrings result = 0 for i in range(n): count = 0 for j in range(i, n): # If the current character # is a vowel if (isVowel(s[j])): #Increase count count += 1 # If substring contains # even number of vowels if (count % 2 == 0): #Increase the answer result += 1 # Print the final answer print(result) # Driver Code if __name__ == '__main__': n = 5 s = "abcde" countSubstrings(s, n) # This code is contributed by Mohit Kumar
C#
// C# program to implement // the above approach using System; class GFG{ // Utility function to check // if a character is a vowel static bool isVowel(char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels static void countSubstrings(String s, int n) { // Stores the count of substrings int result = 0; for(int i = 0; i < n; i++) { int count = 0; for(int j = i; j < n; j++) { // If the current character // is a vowel if (isVowel(s[j])) { // Increase count count++; } // If substring contains // even number of vowels if (count % 2 == 0) // Increase the answer result++; } } // Print the final answer Console.WriteLine(result); } // Driver Code public static void Main(String[] args) { int n = 5; String s = "abcde"; countSubstrings(s, n); } } // This code is contributed by amal kumar choubey
Javascript
<script> // Javascript program to implement // the above approach // Utility function to check // if a character is a vowel function isVowel(c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels function countSubstrings(s, n) { // Stores the count of substrings let result = 0; for(let i = 0; i < n; i++) { let count = 0; for(let j = i; j < n; j++) { // If the current character // is a vowel if (isVowel(s[j])) { // Increase count count++; } // If substring contains // even number of vowels if (count % 2 == 0) // Increase the answer result++; } } // Print the final answer document.write(result); } let n = 5; let s = "abcde"; countSubstrings(s, n); </script>
7
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente:
siga los pasos a continuación para optimizar el enfoque anterior:
- Inicialice una array de módulo de recuento acumulativo temp[] , de modo que:
temp[0] : almacena el recuento de substrings que tienen un número par de vocales.
temp[1] : almacena el recuento de substrings que tienen un número impar de vocales.
- Cualquier substring [S i , S j ] contendrá un número par de vocales si el número de vocales en [S 0 , S i-1 ] y el número de vocales en [S 0 , S j ] tienen la misma paridad, es decir o ambos son pares o ambos impares .
- Dado que el recuento de substrings con un número par de vocales y un número impar de vocales se almacenan en temp[] , entonces, usando el lema de protocolo de enlace :
Recuento total de substrings = (temp[0] * (temp[0] – 1))/2 + (temp[1] * (temp[1] – 1))/2
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Utility function to check // if a character is a vowel bool isVowel(char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels void countSubstrings(string s, int n) { // Stores the count of substrings // with even and odd number of // vowels respectively int temp[] = { 1, 0 }; int result = 0, sum = 0; for(int i = 0; i <= n - 1; i++) { // Update count of vowels modulo 2 // in sum to obtain even or odd sum += (isVowel(s[i]) ? 1 : 0); sum %= 2; // Increment even/odd count temp[sum]++; } // Count substrings with even number // of vowels using Handshaking Lemma result += ((temp[0] * (temp[0] - 1)) / 2); result += ((temp[1] * (temp[1] - 1)) / 2); cout << result; } // Driver Code int main() { int n = 5; string s = "abcde"; countSubstrings(s, n); } // This code is contributed by Amit Katiyar
Java
// Java Program to implement // the above approach class GFG { // Utility function to check // if a character is a vowel static boolean isVowel(char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels static void countSubstrings(String s, int n) { // Stores the count of substrings // with even and odd number of // vowels respectively int temp[] = { 1, 0 }; int result = 0, sum = 0; for (int i = 0; i <= n - 1; i++) { // Update count of vowels modulo 2 // in sum to obtain even or odd sum += (isVowel(s.charAt(i)) ? 1 : 0); sum %= 2; // Increment even/odd count temp[sum]++; } // Count substrings with even number // of vowels using Handshaking Lemma result += ((temp[0] * (temp[0] - 1)) / 2); result += ((temp[1] * (temp[1] - 1)) / 2); System.out.println(result); } // Driver Code public static void main(String[] args) { int n = 5; String s = "abcde"; countSubstrings(s, n); } }
Python3
# Python3 program to implement # the above approach # Utility function to check # if a character is a vowel def isVowel(c): if (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'): return True; return False; # Function to calculate and return the # count of substrings with even number # of vowels def countSubstrings(s, n): # Stores the count of substrings # with even and odd number of # vowels respectively temp = [1, 0]; result = 0; sum = 0; for i in range(0, n): # Update count of vowels modulo 2 # in sum to obtain even or odd sum += (1 if isVowel(s[i]) else 0); sum %= 2; # Increment even/odd count temp[sum] += 1; # Count substrings with even number # of vowels using Handshaking Lemma result += ((temp[0] * (temp[0] - 1)) // 2); result += ((temp[1] * (temp[1] - 1)) // 2); print(result); # Driver Code if __name__ == '__main__': n = 5; s = "abcde"; countSubstrings(s, n); # This code is contributed by amal kumar choubey
C#
// C# Program to implement // the above approach using System; class GFG { // Utility function to check // if a character is a vowel static bool isVowel(char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels static void countSubstrings(String s, int n) { // Stores the count of substrings // with even and odd number of // vowels respectively int []temp = { 1, 0 }; int result = 0, sum = 0; for (int i = 0; i <= n - 1; i++) { // Update count of vowels modulo 2 // in sum to obtain even or odd sum += (isVowel(s[i]) ? 1 : 0); sum %= 2; // Increment even/odd count temp[sum]++; } // Count substrings with even number // of vowels using Handshaking Lemma result += ((temp[0] * (temp[0] - 1)) / 2); result += ((temp[1] * (temp[1] - 1)) / 2); Console.Write(result); } // Driver Code public static void Main(string[] args) { int n = 5; String s = "abcde"; countSubstrings(s, n); } } // This code is contributed by rock_cool
Javascript
<script> // Javascript program to implement // the above approach // Utility function to check // if a character is a vowel function isVowel(c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; return false; } // Function to calculate and return the // count of substrings with even number // of vowels function countSubstrings(s, n) { // Stores the count of substrings // with even and odd number of // vowels respectively let temp = [ 1, 0 ]; let result = 0, sum = 0; for(let i = 0; i <= n - 1; i++) { // Update count of vowels modulo 2 // in sum to obtain even or odd sum += (isVowel(s[i]) ? 1 : 0); sum %= 2; // Increment even/odd count temp[sum]++; } // Count substrings with even number // of vowels using Handshaking Lemma result += ((temp[0] * (temp[0] - 1)) / 2); result += ((temp[1] * (temp[1] - 1)) / 2); document.write(result); } let n = 5; let s = "abcde"; countSubstrings(s, n); // This code is contributed by divyeshrabadiya07. </script>
7
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por jrishabh99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA