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

Dada una string str[] 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 las ocurrencias de la vocal en estas strings = 3.(‘a’ ocurrió 3 veces)

Entrada: str = «daceh» 
Salida: 16

Enfoque de la suma de prefijos: el enfoque ingenuo y el enfoque que usa la suma de prefijos se analizan en el Conjunto 1 de este artículo .

Enfoque eficiente: supongamos que, dado que la string es str , la substring comienza en la posición x y termina en la posición y y si la vocal está en la i-ésima posición, donde 0<=x<=i e i<=y<-N . para cada vocal, podría estar en la substring , es decir, (i+1) opciones para x y (ni) opciones para y . Así que hay un total de (i+1)*(ni) substrings que contienen str[i]. Tome una constante » aeiou «. Siga los pasos a continuación para resolver el problema:

• Inicialice la variable res como 0 para almacenar la respuesta.
• Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
  • Si str[i] es una vocal, agregue el valor de (I+1)*(Ni) a la variable res para contar el número total de vocales posibles.
• Después de realizar los pasos anteriores, imprima el valor de res como respuesta.

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 count the number of vowels
long long countVowels(string str)
{
 
    // Define the size of the string
    // and ans as zero
    long res = 0, N = str.size();
 
    // Start traversing and find if their
    // is any vowel or not
    for (int i = 0; i < N; ++i)
 
        // If there is vowel, then count
        // the numbers of vowels
        if (string("aeiou").find(str[i])
            != string::npos)
            res += (i + 1) * (N - i);
 
    return res;
}
 
// Driver Code
int main()
{
    string str = "daceh";
 
    // Call the function
    long long ans = countVowels(str);
 
    cout << ans << endl;
 
    return 0;
}

// Java program for the above approach
class GFG{
 
  // Function to count the number of vowels
  static long countVowels(String str)
  {
 
    // Define the size of the String
    // and ans as zero
    long res = 0, N = str.length();
 
    // Start traversing and find if their
    // is any vowel or not
    for (int i = 0; i < N; ++i)
 
      // If there is vowel, then count
      // the numbers of vowels
      if (new String("aeiou").contains(String.valueOf(str.charAt(i))))
        res += (i + 1) * (N - i);
 
    return res;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    String str = "daceh";
 
    // Call the function
    long ans = countVowels(str);
    System.out.print(ans +"\n");
 
  }
}
 
// This code is contributed by shikhasingrajput.

# Python program for the above approach
 
# Function to count the number of vowels
def countVowels(str):
   
    # Define the size of the String
    # and ans as zero
    res = 0;
    N = len(str);
 
    # Start traversing and find if their
    # is any vowel or not
    for i in range(N):
 
        # If there is vowel, then count
        # the numbers of vowels
        if ((str[i]) in ("aeiou")):
            res += (i + 1) * (N - i);
    return res;
 
# Driver Code
if __name__ == '__main__':
 
    str = "daceh";
 
    # Call the function
    ans = countVowels(str);
    print(ans);
 
# This code is contributed by 29AjayKumar

// C# program for the above approach
using System;
class GFG{
 
  // Function to count the number of vowels
  static long countVowels(String str)
  {
 
    // Define the size of the String
    // and ans as zero
    long res = 0, N = str.Length;
 
    // Start traversing and find if their
    // is any vowel or not
    for (int i = 0; i < N; ++i)
 
      // If there is vowel, then count
      // the numbers of vowels
      if (new String("aeiou").Contains(str[i]))
        res += (i + 1) * (N - i);
 
    return res;
  }
 
  // Driver Code
  public static void Main()
  {
    String str = "daceh";
 
    // Call the function
    long ans = countVowels(str);
    Console.Write(ans +"\n");
 
  }
}
 
// This code is contributed by gfgking

<script>
// javascript program for the above approach
// Function to count the number of vowels
  function countVowels(str)
  {
 
    // Define the size of the String
    // and ans as zero
    var res = 0, N = str.length;
 
    // Start traversing and find if their
    // is any vowel or not
    for (var i = 0; i < N; ++i)
 
      // If there is vowel, then count
      // the numbers of vowels
      if ("aeiou".includes(str[i]))
        res += (i + 1) * (N - i);
 
    return res;
  }
 
// Driver Code
var str = "daceh";
 
// Call the function
var ans = countVowels(str);
document.write(ans);
 
// This code is contributed by shikhasingrajput
</script>

16

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