Encuentra substrings que contengan todas las vocales

Se nos ha dado una string en letras minúsculas. Necesitamos imprimir substrings que contengan todas las vocales al menos una vez y que no haya consonantes (caracteres que no sean vocales) presentes en las substrings.

Ejemplos:  

Input : str = aeoibddaeoiud
Output : aeoiu

Input : str = aeoibsddaeiouudb
Output : aeiou, aeiouu

Referencia: – Preguntas de la entrevista de Samsung.

Usamos una técnica basada en hashing y comenzamos a atravesar la string desde el principio. Para cada carácter, consideramos todas las substrings a partir de él. Si encontramos una consonante, pasamos al siguiente carácter inicial. De lo contrario, insertamos el carácter actual en un hash. Si se incluyen todas las vocales, imprimimos la substring actual. 

Implementación:

// CPP program to find all substring that
// contain all vowels
#include <bits/stdc++.h>
 
using namespace std;
 
// Returns true if x is vowel.
bool isVowel(char x)
{
    // Function to check whether a character is
    // vowel or not
    return (x == 'a' || x == 'e' || x == 'i' ||
                        x == 'o' || x == 'u');
}
 
void FindSubstring(string str)
{
    set<char> hash; // To store vowels
 
    // Outer loop picks starting character and
    // inner loop picks ending character.
    int n = str.length();
    for (int i = 0; i < n; i++) {
       for (int j = i; j < n; j++) {
 
            // If current character is not vowel,
            // then no more result substrings
            // possible starting from str[i].
            if (isVowel(str[j]) == false)
              break;
 
            // If vowel, then we insert it in hash             
            hash.insert(str[j]);
 
            // If all vowels are present in current
            // substring
            if (hash.size() == 5)
                cout << str.substr(i, j-i+1) << " ";
        }
 
        hash.clear();
    }
}
 
// Driver code
int main()
{
    string str = "aeoibsddaeiouudb";
    FindSubstring(str);
    return 0;
}

// Java program to find all substring that 
// contain all vowels
import java.util.HashSet;
 
public class GFG {
 
    // Returns true if x is vowel.
    static boolean isVowel(char x) {
        // Function to check whether a character is
        // vowel or not
        return (x == 'a' || x == 'e' || x == 'i'
                || x == 'o' || x == 'u');
    }
 
    static void findSubstring(String str) {
        HashSet<Character> hash = new HashSet<Character>();
            // To store vowels
 
        // Outer loop picks starting character and
        // inner loop picks ending character.
        int n = str.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
 
                // If current character is not vowel,
                // then no more result substrings
                // possible starting from str[i].
                if (isVowel(str.charAt(j)) == false)
                    break;
 
                // If vowel, then we insert it in hash
                hash.add(str.charAt(j));
 
                // If all vowels are present in current
                // substring
                if (hash.size() == 5)
                    System.out.print(str.substring(i, j + 1) + " ");
            }
            hash.clear();
        }
    }
 
    // Driver code
    public static void main(String[] args) {
        String str = "aeoibsddaeiouudb";
        findSubstring(str);
    }
}

# Python3 program to find all substring that
# contain all vowels
 
# Returns true if x is vowel.
def isVowel(x):
     
    # Function to check whether a character is
    # vowel or not
    if (x == 'a' or x == 'e' or x == 'i' or
        x == 'o' or x == 'u'):
        return True
    return False
 
def FindSubstring(str1):
 
    # To store vowels
 
    # Outer loop picks starting character and
    # inner loop picks ending character.
    n = len(str1)
    for i in range(n):
        hash = dict()
        for j in range(i, n):
 
            # If current character is not vowel,
            # then no more result substrings
            # possible starting from str1[i].
            if (isVowel(str1[j]) == False):
                break
 
            # If vowel, then we insert it in hash
            hash[str1[j]] = 1
 
            # If all vowels are present in current
            # substring
            if (len(hash) == 5):
                print(str1[i:j + 1], end = " ")
 
# Driver code
str1 = "aeoibsddaeiouudb"
FindSubstring(str1)
 
# This code is contributed by Mohit Kumar

// C# program to find all substring that
// contain all vowels
using System;
using System.Collections.Generic;
 
public class GFG
{
 
// Returns true if x is vowel.
public static bool isVowel(char x)
{
    // Function to check whether a
    // character is vowel or not
    return (x == 'a' || x == 'e' ||
            x == 'i' || x == 'o' || x == 'u');
}
 
public static void findSubstring(string str)
{
    HashSet<char> hash = new HashSet<char>();
     
    // To store vowels    
    // Outer loop picks starting character and
    // inner loop picks ending character.
    int n = str.Length;
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
 
            // If current character is not vowel,
            // then no more result substrings
            // possible starting from str[i].
            if (isVowel(str[j]) == false)
            {
                break;
            }
 
            // If vowel, then we insert it in hash
            hash.Add(str[j]);
 
            // If all vowels are present in current
            // substring
            if (hash.Count == 5)
            {
                Console.Write(str.Substring(i,     
                             (j + 1) - i) + " ");
            }
        }
        hash.Clear();
    }
}
 
// Driver code
public static void Main(string[] args)
{
    string str = "aeoibsddaeiouudb";
    findSubstring(str);
}
}
 
// This code is contributed by Shrikant13

<script>
// Javascript program to find all substring that 
// contain all vowels
     
    // Returns true if x is vowel.
    function isVowel(x)
    {
        // Function to check whether a character is
        // vowel or not
        return (x == 'a' || x == 'e' || x == 'i'
                || x == 'o' || x == 'u');       
    }
     
    function findSubstring(str)
    {
        let hash = new Set();
            // To store vowels
   
        // Outer loop picks starting character and
        // inner loop picks ending character.
        let n = str.length;
        for (let i = 0; i < n; i++) {
            for (let j = i; j < n; j++) {
   
                // If current character is not vowel,
                // then no more result substrings
                // possible starting from str[i].
                if (isVowel(str[j]) == false)
                    break;
   
                // If vowel, then we insert it in hash
                hash.add(str[j]);
   
                // If all vowels are present in current
                // substring
                if (hash.size == 5)
                    document.write(str.substring(i, j + 1) + " ");
            }
            hash.clear();
        }
    }
     
    // Driver code
    let str = "aeoibsddaeiouudb";
    findSubstring(str);
 
 
// This code is contributed by patel2127
</script>

aeiou aeiouu 

Complejidad del tiempo : O(n ² )

Solución optimizada: para cada carácter, si el carácter actual es una vocal, insértelo en hash. De lo contrario, establezca el indicador Inicio en la siguiente substring a partir del índice i+1. Si se incluyen todas las vocales, imprimimos la substring actual. 

Implementación:

// C++ program to find all substring that
// contain all vowels
#include<bits/stdc++.h>
 
using namespace std;
 
// Returns true if x is vowel.
bool isVowel(char x)
{
    // Function to check whether a character is
    // vowel or not
    return (x == 'a' || x == 'e' || x == 'i' ||
                        x == 'o' || x == 'u');
}
 
// Function to FindSubstrings of string
void FindSubstring(string str)
{
    set<char> hash;  // To store vowels
 
    int start = 0;
    for (int i=0; i<str.length(); i++)
    {
        // If current character is vowel then
        // insert into hash ,
        if (isVowel(str[i]) == true)
        {
            hash.insert(str[i]);
 
            // If all vowels are present in current
            // substring
            if (hash.size()==5)
                cout << str.substr(start, i-start+1)
                     << " ";
        }
        else
        {
            start = i+1;
            hash.clear();
        }
    }
}
 
// Driver Code
int main()
{
    string str = "aeoibsddaeiouudb";
    FindSubstring(str);
    return 0;
}

// Java program to find all substring that 
// contain all vowels
import java.util.HashSet;
 
public class GFG {
 
    // Returns true if x is vowel.
    static boolean isVowel(char x) {
        // Function to check whether a character is
        // vowel or not
        return (x == 'a' || x == 'e' || x == 'i'
                || x == 'o' || x == 'u');
    }
 
    // Function to FindSubstrings of string
    static void findSubstring(String str) {
        HashSet<Character> hash = new HashSet<Character>();
        // To store vowels
 
        int start = 0;
        for (int i = 0; i < str.length(); i++) {
            // If current character is vowel then
            // insert into hash ,
            if (isVowel(str.charAt(i)) == true) {
                hash.add(str.charAt(i));
 
                // If all vowels are present in current
                // substring
                if (hash.size() == 5)
                    System.out.print(str.substring(start, i + 1) + " ");
            } else {
                start = i + 1;
                hash.clear();
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args) {
        String str = "aeoibsddaeiouudb";
        findSubstring(str);
    }
 
}

# Python3 program to find all substring
# that contain all vowels
 
# Returns true if x is vowel.
def isVowel(x):
     
    # Function to check whether
    # a character is vowel or not
    return (x == 'a' or x == 'e' or
            x == 'i' or x == 'o' or
            x == 'u');
 
# Function to FindSubstrings of string
def FindSubstring(str):
 
    hash = set(); # To store vowels
 
    start = 0;
    for i in range(len(str)):
         
        # If current character is vowel
        # then insert into hash
        if (isVowel(str[i]) == True):
            hash.add(str[i]);
 
            # If all vowels are present
            # in current substring
            if (len(hash) == 5):
                print(str[start : i + 1],
                              end = " ");
        else:
            start = i + 1;
            hash.clear();
 
# Driver Code
str = "aeoibsddaeiouudb";
FindSubstring(str);
 
# This code is contributed by 29AjayKumar

using System;
using System.Collections.Generic;
 
// c# program to find all substring that  
// contain all vowels 
 
public class GFG
{
 
    // Returns true if x is vowel.
    public static bool isVowel(char x)
    {
        // Function to check whether a character is
        // vowel or not
        return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u');
    }
 
    // Function to FindSubstrings of string
    public static void findSubstring(string str)
    {
        HashSet<char> hash = new HashSet<char>();
        // To store vowels
 
        int start = 0;
        for (int i = 0; i < str.Length; i++)
        {
            // If current character is vowel then
            // insert into hash ,
            if (isVowel(str[i]) == true)
            {
                hash.Add(str[i]);
 
                // If all vowels are present in current
                // substring
                if (hash.Count == 5)
                {
                    Console.Write(str.Substring(start, (i + 1) - start) + " ");
                }
            }
            else
            {
                start = i + 1;
                hash.Clear();
            }
        }
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        string str = "aeoibsddaeiouudb";
        findSubstring(str);
    }
 
}
 
// This code is contributed by Shrikant13

<script>
 
// Javascript program to find all substring that
// contain all vowels
     
// Returns true if x is vowel.
function isVowel(x)
{
     
    // Function to check whether a character is
    // vowel or not
    return (x == 'a' || x == 'e' || x == 'i' ||
            x == 'o' || x == 'u');
}
 
// Function to FindSubstrings of string
function findSubstring(str)
{
    let hash = new Set();
     
    // To store vowels
    let start = 0;
    for(let i = 0; i < str.length; i++)
    {
         
        // If current character is vowel then
        // insert into hash ,
        if (isVowel(str[i]) == true)
        {
            hash.add(str[i]);
 
            // If all vowels are present in current
            // substring
            if (hash.size == 5)
                document.write(
                    str.substring(start, i + 1) + " ");
        }
        else
        {
            start = i + 1;
            hash.clear();
        }
    }
}
 
// Driver Code
let str = "aeoibsddaeiouudb";
findSubstring(str);
 
// This code is contributed by unknown2108
 
</script>

aeiou aeiouu 

Complejidad temporal : O(n)
Espacio auxiliar: O(n)

Gracias a Kriti Shukla por sugerir esta solución optimizada.
Este artículo es una contribución de Ashish Madaan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.