Cuente el número de vocales que ocurren en todas las substrings de una string dada

Dada una string de longitud N de caracteres en minúscula que contiene 0 o más vocales, la tarea es encontrar el recuento de vocales que se produjeron en todas las substrings de la string dada.
Ejemplos: 
 

Entrada: str = “abc” 
Salida: 3
La string dada “abc” contiene solo una vocal = ‘a’ Las 
substrings de “abc” son = {“a”, “b”, “c”, “ab”, “bc , “abc”} 
Por lo tanto, la suma de ocurrencias de la vocal en estas strings = 3.(‘a’ ocurrió 3 veces)
Entrada: str = “daceh” 
Salida: 16

Enfoque ingenuo: dada una string de longitud N, el número de substrings que se pueden formar = N (N + 1)/2. Una solución simple es para cada substring, contamos las apariciones de las vocales y las sumamos para obtener el resultado. La complejidad temporal de este enfoque es O(N ³ ), que no es adecuada para valores grandes de N.
Enfoque eficiente: la idea es utilizar una técnica basada en arrays de suma de prefijos en la que almacenamos las ocurrencias de cada carácter en todas las substrings concatenadas . 
 

• Para el primer personaje, 
   

no. de ocurrencias = no. de substrings que comienzan con el primer carácter = N.

• Para cada uno de los siguientes caracteres, almacenamos el 
   

no. de substrings que comienzan con ese carácter + el número de substrings formadas por los caracteres anteriores que contienen este carácter – el número de substrings formadas solo por los caracteres anteriores.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Returns the total sum of
// occurrences of all vowels
int vowel_calc(string s)
{
    int n = s.length();
    vector<int> arr;
 
    for (int i = 0; i < n; i++) {
 
        if (i == 0)
            // No. of occurrences of 0th character
            // in all the substrings
            arr.push_back(n);
 
        else
            // No. of occurrences of the ith character
            // in all the substrings
            arr.push_back((n - i) + arr[i - 1] - i);
    }
 
    int sum = 0;
    for (int i = 0; i < n; i++)
 
        // Check if ith character is a vowel
        if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i'
            || s[i] == 'o' || s[i] == 'u')
            sum += arr[i];
 
    // Return the total sum
    // of occurrences of vowels
    return sum;
}
 
// Driver code
int main()
{
    string s = "daceh";
    cout << vowel_calc(s) << endl;
 
    return 0;
}

// Java implementation of the above approach
 
import java.io.*;
import java.util.*;
 
public class Gfg {
 
    // Returns the total sum of
    // occurrences of all vowels
    static int vowel_calc(String s)
    {
        int n = s.length();
        int arr[] = new int[n];
 
        for (int i = 0; i < n; i++) {
 
            if (i == 0)
                // No. of occurrences of 0th character
                // in all the substrings
                arr[i] = n;
 
            else
                // No. of occurrences of ith character
                // in all the substrings
                arr[i] = (n - i) + arr[i - 1] - i;
        }
 
        int sum = 0;
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            // Check if ith character is a vowel
            if (ch == 'a' || ch == 'e' || ch == 'i'
                || ch == 'o' || ch == 'u')
                sum += arr[i];
        }
 
        // Return the total sum
        // of occurrences of vowels
        return sum;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        String s = "daceh";
        System.out.println(vowel_calc(s));
    }
}

# Python 3 implementation of
# a more efficient approach.
# return sum of all occurrences of all vowels
def sumVowel(string):
    n = len(string)
    sum = 0
    string = string.lower()
 
    # iterate through every character in the string
    for i in range(0, n):
        s = string[i]
 
        # checks if the character is a vowel or not
        if (s=="a" or s == "e" or s == "i" or s == "o" or s == "u"):
 
            # uses below expression to calculate the count
                        # of all occurrences of character in substrings
                        # of the string
            sum += ((n - i) * (i + 1))           
 
    # return the total sum of occurrence
    return sum
 
#driver code
if __name__ == '__main__':
    #input string here
    string = "abhay"
    #print returned sum
    print(sumVowel(string))
 
# This code is contributed by
# Abhay Subramanian K

// C# implementation of the above approach
  
 
using System;
  
public class Gfg {
  
    // Returns the total sum of
    // occurrences of all vowels
    static int vowel_calc(string s)
    {
        int n = s.Length;
        int[] arr = new int[n];
  
        for (int i = 0; i < n; i++) {
  
            if (i == 0)
                // No. of occurrences of 0th character
                // in all the substrings
                arr[i] = n;
  
            else
                // No. of occurrences of ith character
                // in all the substrings
                arr[i] = (n - i) + arr[i - 1] - i;
        }
  
        int sum = 0;
        for (int i = 0; i < n; i++) {
            char ch = s[i];
            // Check if ith character is a vowel
            if (ch == 'a' || ch == 'e' || ch == 'i'
                || ch == 'o' || ch == 'u')
                sum += arr[i];
        }
  
        // Return the total sum
        // of occurrences of vowels
        return sum;
    }
  
    // Driver Code
    public static void Main()
    {
        string s = "daceh";
        Console.Write(vowel_calc(s));
    }
}

<?php
// PHP implementation of the above approach
 
// Returns the total sum of
// occurrences of all vowels
function vowel_calc($s)
{
    $n = strlen($s);
    $arr = array();
 
    for ($i = 0; $i < $n; $i++)
    {
        if ($i == 0)
         
            // No. of occurrences of 0th character
            // in all the substrings
            $arr[$i] = $n;
 
        else
         
            // No. of occurrences of ith character
            // in all the substrings
            $arr[$i] = ($n - $i) + $arr[$i - 1] - $i;
        }
 
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
    {
         
        // Check if ith character is a vowel
        if ($s[$i] == 'a' || $s[$i] == 'e' ||
            $s[$i] == 'i' || $s[$i] == 'o' ||
            $s[$i] == 'u')
            $sum += $arr[$i];
        }
 
        // Return the total sum
        // of occurrences of vowels
        return $sum;
    }
 
// Driver Code
$s = "daceh";
echo(vowel_calc($s));
 
// This code is contributed by Shivi_Aggarwal
?>

<script>
 
// Javascript implementation of the above approach
 
// Returns the total sum of
// occurrences of all vowels
function vowel_calc(s)
{
    var n = s.length;
    var arr = [];
 
    for (var i = 0; i < n; i++) {
 
        if (i == 0)
            // No. of occurrences of 0th character
            // in all the substrings
            arr.push(n);
 
        else
            // No. of occurrences of the ith character
            // in all the substrings
            arr.push((n - i) + arr[i - 1] - i);
    }
 
    var sum = 0;
    for (var i = 0; i < n; i++)
 
        // Check if ith character is a vowel
        if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i'
            || s[i] == 'o' || s[i] == 'u')
            sum += arr[i];
 
    // Return the total sum
    // of occurrences of vowels
    return sum;
}
 
// Driver code
var s = "daceh";
document.write( vowel_calc(s));
 
// This code is contributed by importantly.
</script>

16

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(N)