Cuente las substrings que contienen todas las vocales | CONJUNTO 2

Dada una string str que contiene letras en minúsculas, la tarea es contar las substrings que contienen todas las vocales al menos una vez y no hay consonantes (caracteres que no sean vocales) presentes en las substrings. 
Ejemplos: 
 

Entrada: str = “aeoibsddaaeiouudb” 
Salida: 4 
“aaeiouu”, “aeiouu”, “aeiou” y “aaeiou”
Entrada: str = “aeoisbddiouuaedf” 
Salida: 1
Entrada: str = “aeouisddaaeeiouua” 
Salida: 9 
 

Enfoque: la idea es extraer todas las substrings de longitud máxima que contienen solo vocales. Ahora, para todas estas substrings por separado, necesitamos encontrar la cantidad de substrings que contienen todas las vocales al menos una vez. Esto se puede hacer usando la técnica de dos puntos . 
Ilustración de cómo usar la técnica de dos puntos en este caso: 
 

If string = “aeoibsddaaeiouudb” 
El primer paso es extraer todas las substrings de longitud máxima que contienen solo vocales que son: 
 

1. aeoi
2. aaeiouu

Ahora, tome la primera string “aeoi”, no se contará porque falta la vocal ‘u’. 
Luego, tome la segunda substring, es decir, «aaeiouu». 
Longitud de la string, n = 7 
inicio = 0 
índice = 0 
conteo = 0 
Haremos un ciclo hasta que todas las vocales estén presentes al menos una vez, por lo que nos detendremos en el índice 5 y comenzaremos = 0. 
Ahora nuestra string es “aaeiou” y hay n – i substrings que contienen vocales al menos una vez y tienen la string “aaeiou” como prefijo. 
Estas substrings son: “aaeiou”, “aaeiouu” 
cuenta = cuenta + (n – i) = 7 – 5 = 2 
Ahora, cuenta = 2
Luego, el incremento comienza con 1. Si la substring está entre [inicio, índice], es decir (1, 5) todavía contiene vocales al menos una vez, luego agregue (n – i). 
Estas substrings son: “aeiou”, “aeiouu” 
cuenta = cuenta + (n – i) = 7 – 5 = 2 
Ahora, cuenta = 2
Luego comienza = 2, ahora la substring se convierte en “eiouu”. Entonces no se puede agregar más conteo porque falta la vocal ‘a’. 
 

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if c is a vowel
bool isVowel(char c)
{
    return (c == 'a' || c == 'e' || c == 'i'
            || c == 'o' || c == 'u');
}
 
// Function to return the count of sub-strings
// that contain every vowel at least
// once and no consonant
int countSubstringsUtil(string s)
{
    int count = 0;
 
    // Map is used to store count of each vowel
    map<char, int> mp;
 
    int n = s.length();
 
    // Start index is set to 0 initially
    int start = 0;
 
    for (int i = 0; i < n; i++) {
        mp[s[i]]++;
 
        // If substring till now have all vowels
        // atleast once increment start index until
        // there are all vowels present between
        // (start, i) and add n - i each time
        while (mp['a'] > 0 && mp['e'] > 0
               && mp['i'] > 0 && mp['o'] > 0
               && mp['u'] > 0) {
            count += n - i;
            mp[s[start]]--;
            start++;
        }
    }
 
    return count;
}
 
// Function to extract all maximum length
// sub-strings in s that contain only vowels
// and then calls the countSubstringsUtil() to find
// the count of valid sub-strings in that string
int countSubstrings(string s)
{
    int count = 0;
    string temp = "";
 
    for (int i = 0; i < s.length(); i++) {
 
        // If current character is a vowel then
        // append it to the temp string
        if (isVowel(s[i])) {
            temp += s[i];
        }
 
        // The sub-string containing all vowels ends here
        else {
 
            // If there was a valid sub-string
            if (temp.length() > 0)
                count += countSubstringsUtil(temp);
 
            // Reset temp string
            temp = "";
        }
    }
 
    // For the last valid sub-string
    if (temp.length() > 0)
        count += countSubstringsUtil(temp);
 
    return count;
}
 
// Driver code
int main()
{
    string s = "aeouisddaaeeiouua";
 
    cout << countSubstrings(s) << endl;
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function that returns true if c is a vowel
static boolean isVowel(char c)
{
    return (c == 'a' || c == 'e' ||
            c == 'i' || c == 'o' || c == 'u');
}
 
// Function to return the count of sub-strings
// that contain every vowel at least
// once and no consonant
static int countSubstringsUtil(char []s)
{
    int count = 0;
 
    // Map is used to store count of each vowel
    Map<Character, Integer> mp = new HashMap<>();
 
    int n = s.length;
 
    // Start index is set to 0 initially
    int start = 0;
 
    for (int i = 0; i < n; i++)
    {
        if(mp.containsKey(s[i]))
        {
            mp.put(s[i], mp.get(s[i]) + 1);
        }
        else
        {
            mp.put(s[i], 1);
        }
 
        // If substring till now have all vowels
        // atleast once increment start index until
        // there are all vowels present between
        // (start, i) and add n - i each time
        while (mp.containsKey('a') && mp.containsKey('e') &&
               mp.containsKey('i') && mp.containsKey('o') &&
               mp.containsKey('u') && mp.get('a') > 0 &&
               mp.get('e') > 0 && mp.get('i') > 0 &&
               mp.get('o') > 0 && mp.get('u') > 0)
        {
            count += n - i;
            mp.put(s[start], mp.get(s[start]) - 1);
 
            start++;
        }
    }
    return count;
}
 
// Function to extract all maximum length
// sub-strings in s that contain only vowels
// and then calls the countSubstringsUtil() to find
// the count of valid sub-strings in that string
static int countSubstrings(String s)
{
    int count = 0;
    String temp = "";
 
    for (int i = 0; i < s.length(); i++)
    {
 
        // If current character is a vowel then
        // append it to the temp string
        if (isVowel(s.charAt(i)))
        {
            temp += s.charAt(i);
        }
 
        // The sub-string containing all vowels ends here
        else
        {
 
            // If there was a valid sub-string
            if (temp.length() > 0)
                count += countSubstringsUtil(temp.toCharArray());
 
            // Reset temp string
            temp = "";
        }
    }
 
    // For the last valid sub-string
    if (temp.length() > 0)
        count += countSubstringsUtil(temp.toCharArray());
 
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    String s = "aeouisddaaeeiouua";
 
    System.out.println(countSubstrings(s));
}
}
 
// This code is contributed by Princi Singh

# Python3 implementation of the approach
 
# Function that returns true if c is a vowel
def isVowel(c) :
 
    return (c == 'a' or c == 'e' or c == 'i'
            or c == 'o' or c == 'u');
 
 
# Function to return the count of sub-strings
# that contain every vowel at least
# once and no consonant
def countSubstringsUtil(s) :
 
    count = 0;
 
    # Map is used to store count of each vowel
    mp = dict.fromkeys(s,0);
 
    n = len(s);
 
    # Start index is set to 0 initially
    start = 0;
 
    for i in range(n) :
        mp[s[i]] += 1;
 
        # If substring till now have all vowels
        # atleast once increment start index until
        # there are all vowels present between
        # (start, i) and add n - i each time
        while (mp['a'] > 0 and mp['e'] > 0
            and mp['i'] > 0 and mp['o'] > 0
            and mp['u'] > 0) :
            count += n - i;
            mp[s[start]] -= 1;
            start += 1;
 
    return count;
 
# Function to extract all maximum length
# sub-strings in s that contain only vowels
# and then calls the countSubstringsUtil() to find
# the count of valid sub-strings in that string
def countSubstrings(s) :
 
    count = 0;
    temp = "";
 
    for i in range(len(s)) :
 
        # If current character is a vowel then
        # append it to the temp string
        if (isVowel(s[i])) :
            temp += s[i];
 
        # The sub-string containing all vowels ends here
        else :
 
            # If there was a valid sub-string
            if (len(temp) > 0) :
                count += countSubstringsUtil(temp);
 
            # Reset temp string
            temp = "";
 
    # For the last valid sub-string
    if (len(temp) > 0) :
        count += countSubstringsUtil(temp);
 
    return count;
 
# Driver code
if __name__ == "__main__" :
 
    s = "aeouisddaaeeiouua";
 
    print(countSubstrings(s));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function that returns true if c is a vowel
static bool isVowel(char c)
{
    return (c == 'a' || c == 'e' ||
            c == 'i' || c == 'o' || c == 'u');
}
 
// Function to return the count of sub-strings
// that contain every vowel at least
// once and no consonant
static int countSubstringsUtil(char []s)
{
    int count = 0;
 
    // Map is used to store count of each vowel
    Dictionary<char,
               int> mp = new Dictionary<char,
                                        int>();
 
    int n = s.Length;
 
    // Start index is set to 0 initially
    int start = 0;
 
    for (int i = 0; i < n; i++)
    {
        if(mp.ContainsKey(s[i]))
        {
            mp[s[i]] = mp[s[i]] + 1;
        }
        else
        {
            mp.Add(s[i], 1);
        }
 
        // If substring till now have all vowels
        // atleast once increment start index until
        // there are all vowels present between
        // (start, i) and add n - i each time
        while (mp.ContainsKey('a') && mp.ContainsKey('e') &&
               mp.ContainsKey('i') && mp.ContainsKey('o') &&
               mp.ContainsKey('u') && mp['a'] > 0 &&
               mp['e'] > 0 && mp['i'] > 0 &&
               mp['o'] > 0 && mp['u'] > 0)
        {
            count += n - i;
            if(mp.ContainsKey(s[start]))
                mp[s[start]] = mp[s[start]] - 1;
 
            start++;
        }
    }
    return count;
}
 
// Function to extract all maximum length
// sub-strings in s that contain only vowels
// and then calls the countSubstringsUtil() to find
// the count of valid sub-strings in that string
static int countSubstrings(String s)
{
    int count = 0;
    String temp = "";
 
    for (int i = 0; i < s.Length; i++)
    {
 
        // If current character is a vowel then
        // append it to the temp string
        if (isVowel(s[i]))
        {
            temp += s[i];
        }
 
        // The sub-string containing
        // all vowels ends here
        else
        {
 
            // If there was a valid sub-string
            if (temp.Length > 0)
                count += countSubstringsUtil(temp.ToCharArray());
 
            // Reset temp string
            temp = "";
        }
    }
 
    // For the last valid sub-string
    if (temp.Length > 0)
        count += countSubstringsUtil(temp.ToCharArray());
 
    return count;
}
 
// Driver code
public static void Main(String[] args)
{
    String s = "aeouisddaaeeiouua";
 
    Console.WriteLine(countSubstrings(s));
}
}
 
// This code is contributed by Princi Singh

<script>
// JavaScript implementation of the approach
 
// Function that returns true if c is a vowel
function isVowel( c)
{
    return (c == 'a' || c == 'e' || c == 'i'
            || c == 'o' || c == 'u');
}
 
// Function to return the count of sub-strings
// that contain every vowel at least
// once and no consonant
function countSubstringsUtil( s)
{
    var count = 0;
 
    // Map is used to store count of each vowel
    var mp = {};
 
    var n = s.length;
  
 
    // Start index is set to 0 initially
    var start = 0;
 
    for (let i = 0; i < n; i++) {
        if(mp[s[i]]){
           mp[s[i]]++;
        }
        else
            mp[s[i]] = 1;
         
        
        // If substring till now have all vowels
        // atleast once increment start index until
        // there are all vowels present between
        // (start, i) and add n - i each time
       
        while (mp['a'] > 0 && mp['e'] > 0
               && mp['i'] > 0 && mp['o'] > 0
               && mp['u'] > 0) {
            count += n - i;
            mp[s[start]]--;
            start++;
        }
    }
   
    return count;
}
 
// Function to extract all maximum length
// sub-strings in s that contain only vowels
// and then calls the countSubstringsUtil() to find
// the count of valid sub-strings in that string
function countSubstrings( s)
{
    var count = 0;
    var temp = "";
 
    for (let i = 0; i < s.length; i++) {
 
        // If current character is a vowel then
        // append it to the temp string
        if (isVowel(s[i])) {
            temp += s[i];
        }
 
        // The sub-string containing all vowels ends here
        else {
 
            // If there was a valid sub-string
            if (temp.length > 0)
                count += countSubstringsUtil(temp);
 
            // Reset temp string
            temp = "";
        }
    }
 
    // For the last valid sub-string
    if (temp.length > 0)
        count += countSubstringsUtil(temp);
 
    return count;
}
 
// Driver code
 
var s = "aeouisddaaeeiouua";
console.log( countSubstrings(s));
 
// This code is contributed by ukasp.   
 
</script>

9

Complejidad de Tiempo: O(N), ya que corre un bucle de 0 a (n – 1)

Espacio auxiliar : O(N), ya que se utiliza Hashmap y se asigna memoria en cada iteración.