Conteo de substrings que consisten en un número par de vocales

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++ 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 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 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# 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

<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 ² )
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 ₀ , S _i-1 ] y el número de vocales en [S ₀ , 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++ 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 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 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# 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

<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)