String dada str de tamaño N que consta de letras inglesas mayúsculas y minúsculas. La tarea es encontrar todas las substrings únicas que contengan solo vocales.
Ejemplos:
Entrada: str = «GeeksforGeeks»
Salida: «ee», «e», «o»
Explicación: Hay varias apariciones de algunas de las substrings como «ee», pero estas son las únicas substrings únicas.Entrada: str = “TRAnsmisión”
Salida: “A”, “io”, “i”, “o”Entrada: str = “AioutraevbcUoee”
Salida: “Aiou”, “Aio”, “Ai”, “A”, “iou”, “io”, “i”, “ou”, “o”, “u”, “ ae”,
“a”, “e”, “Uoee”, “Uoe”, “Uo”, ” U”, “oee”, “oe”, “ee”
Enfoque ingenuo: el enfoque más simple es generar todas las substrings y verificar cada una de ellas si contienen solo vocales o no y si son únicas. Usa los siguientes pasos:
- Genera todas las substrings de la string.
- Utilice el mapa para realizar un seguimiento de las substrings únicas.
- Si la substring consta solo de vocales y no está en el mapa, agréguela al mapa y guárdela como respuesta.
- Imprime todas las respuestas
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a character is vowel
bool isvowel(char ch)
{
return (ch == 'a' or ch == 'A' or
ch == 'e' or ch == 'E'
or ch == 'i' or ch == 'I'
or ch == 'o' or ch == 'O' or
ch == 'u' or ch == 'U');
}
// Function to check whether
// string contains only vowel
bool isvalid(string& s)
{
int n = s.length();
for (int i = 0; i < n; i++) {
// Check if the character is
// not vowel then invalid
if (!isvowel(s[i]))
return false;
}
return true;
}
// Function for generating
// all unique substrings of only vowels.
void generateVowelSubstrings(string params)
{
int ans = 0;
unordered_map<string, bool> map;
// Generate all substring of string
for (int i = 0; i < params.length();
i++) {
string temp = "";
for (int j = i; j < params.length();
j++) {
temp += params[j];
// If temp contains only vowels
if (isvalid(temp)) {
map[temp] = true;
}
}
}
unordered_map<string, bool>::iterator itr;
for (itr = map.begin(); itr != map.end();
++itr) {
// Printing all unique substrings.
cout << itr->first << '\n';
}
}
// Driver code
int main()
{
string str = "GeeksForGeeks";
generateVowelSubstrings(str);
return 0;
}
Java
/*package whatever //do not write package name here */
// Java code to implement the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to check if a character is vowel
public static boolean isVowel(char ch)
{
return (ch == 'a' || ch == 'A' || ch == 'e'
|| ch == 'E' || ch == 'i' || ch == 'I'
|| ch == 'o' || ch == 'O' || ch == 'u'
|| ch == 'U');
}
// Function to check whether
// string contains only vowel
public static boolean isValid(String s)
{
int n = s.length();
for (int i = 0; i < n; i++) {
// Check if the character is
// not vowel then invalid
if (!isVowel(s.charAt(i)))
return false;
}
return true;
}
// Function for generating unique substrings of vowels.
public static void
generateVowelSubstrings(String string)
{
int ans = 0;
HashMap<String, Boolean> map = new HashMap<>();
// Generate all subString of s
for (int i = 0; i < string.length(); i++) {
String temp = "";
for (int j = i; j < string.length(); j++)
{
temp += string.charAt(j);
// If temp contains only vowels
if (isValid(temp))
{
// store it only if substring is absent
// in map.
map.putIfAbsent(temp, true);
}
}
}
for (String key : map.keySet())
{
// printing all unique substring.
System.out.println(key);
}
}
// Driver Code
public static void main(String[] args)
{
String str = "GeeksForGeeks";
generateVowelSubstrings(str);
}
}
// This code is contributed by kaalel.
Python3
# JavaScript code to implement above approach
# Function to check if a character is vowel
def isVowel(c):
# Checking for vowels.
return ((c == "a") or (c == "A") or
(c == "e") or (c == "E") or
(c == "i") or (c == "I") or
(c == "o") or (c == "O") or
(c == "u") or (c == "U"))
# Extracting all the maximum length
# sub-strings that contain only vowels.
def vowelSubstrings(params):
str = ""
# Using map to remove identicals
# substrings. e.g. AiotrfAio has 2 "Aio".
map = {}
for i in range(len(params)):
subString = params[i: i + 1]
if(isVowel(subString)):
str += subString
else:
# Storing a substring only if
# it is not empty.
if len(str) != 0:
map[str] = True
str = ""
if (len(str) != 0):
map[str] = True
return map
# Function to generate all unique substrings
# containing only vowels
def generateVowelSubstrings(params):
substringMap = vowelSubstrings(params)
map = {}
# map iterator.
for itr in substringMap:
x = itr
# For each substring stored in map
# generate all possible substrings.
for i in range(len(x)):
for l in range(1,len(x) - i+1):
# Storing the generated
# substring if it is
# absent in the map.
map[x[i:i + l]] = True
for itr in map:
# Printing all values in map.
print(itr)
# Driver code
str = "GeeksForGeeks"
generateVowelSubstrings(str)
# This code is contributed by shinjanpatra
C#
/*package whatever //do not write package name here */
// C# code to implement the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to check if a character is vowel
public static bool isVowel(char ch)
{
return (ch == 'a' || ch == 'A' || ch == 'e'
|| ch == 'E' || ch == 'i' || ch == 'I'
|| ch == 'o' || ch == 'O' || ch == 'u'
|| ch == 'U');
}
// Function to check whether
// string contains only vowel
public static bool isValid(string s)
{
int n = s.Length;
for (int i = 0; i < n; i++) {
// Check if the character is
// not vowel then invalid
if (!isVowel(s[i]))
return false;
}
return true;
}
// Function for generating unique substrings of vowels.
public static void generateVowelSubstrings(string str)
{
Dictionary<string, bool> map
= new Dictionary<string, bool>();
// Generate all subString of s
for (int i = 0; i < str.Length; i++) {
string temp = "";
for (int j = i; j < str.Length; j++) {
temp += str[j];
// If temp contains only vowels
if (isValid(temp)) {
// store it only if substring is absent
// in map.
if (!map.ContainsKey(temp))
map[temp] = true;
}
}
}
foreach(KeyValuePair<string, bool> i in map)
{
// printing all unique substring.
Console.WriteLine(i.Key);
}
}
// Driver Code
public static void Main(string[] args)
{
string str = "GeeksForGeeks";
generateVowelSubstrings(str);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Function to check if a character is vowel
function isvowel(ch)
{
return (ch == 'a' || ch == 'A' || ch == 'e' ||
ch == 'E' || ch == 'i' || ch == 'I' ||
ch == 'o' || ch == 'O' || ch == 'u' ||
ch == 'U');
}
// Function to check whether
// string contains only vowel
function isvalid(s)
{
let n = s.length;
for(let i = 0; i < n; i++)
{
// Check if the character is
// not vowel then invalid
if (!isvowel(s[i]))
return false;
}
return true;
}
// Function for generating all unique
// substrings of only vowels.
function generateVowelSubstrings(params)
{
let ans = 0;
let map = {};
// Generate all substring of string
for(let i = 0; i < params.length; i++)
{
let temp = "";
for(let j = i; j < params.length; j++)
{
temp += params[j];
// If temp contains only vowels
if (isvalid(temp))
{
map[temp] = true;
}
}
}
Object.keys(map).forEach(function (key)
{
document.write(key + '<br>');
});
}
// Driver code
let str = "GeeksForGeeks";
generateVowelSubstrings(str);
// This code is contributed by Potta Lokesh
</script>
Producción
o e ee
Tiempo Complejidad: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente: un mejor enfoque para resolver este problema es extraer todas las substrings de longitud máxima que contienen solo vocales. Ahora, para todas estas substrings por separado, genere substrings únicas que contengan solo las vocales con la ayuda de un mapa. Siga los pasos que se mencionan a continuación:
- Almacene todas las substrings de longitud máxima que contienen solo vocales (por ejemplo, para «Geeksaioer», la longitud máxima es «ee» y «aioe»).
- Use estas substrings y genere los segmentos más pequeños a partir de estas substrings y use el mapa para encontrar las únicas.
- Imprime todas las strings únicas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a character is vowel
bool isVowel(string c)
{
// Checking for vowels.
return ((c == "a") || (c == "A") ||
(c == "e") || (c == "E") ||
(c == "i") || (c == "I") ||
(c == "o") || (c == "O") ||
(c == "u") || (c == "U"));
}
// Extracting all the maximum length
// sub-strings that contain only vowels.
unordered_map<string, bool> vowelSubstrings(
string params)
{
string str;
// Using map to remove identicals
// substrings. e.g. AiotrfAio has 2 "Aio".
unordered_map<string, bool> map;
for (int i = 0; i < params.length();
i++) {
string subString = params.substr(i, 1);
if (isVowel(subString)) {
str += subString;
}
else {
// Storing a substring only if
// it is not empty.
if (!str.empty())
map[str] = true;
str = "";
}
}
if (!str.empty())
map[str] = true;
return map;
}
// Function to generate all unique substrings
// containing only vowels
void generateVowelSubstrings(string params)
{
unordered_map<string, bool> substringMap
= vowelSubstrings(params);
unordered_map<string, bool> map;
// map iterator.
unordered_map<string, bool>::iterator itr;
for (itr = substringMap.begin();
itr != substringMap.end(); ++itr) {
string x = itr->first;
// For each substring stored in map
// generate all possible substrings.
for (int i = 0; i < x.length(); i++) {
for (int len = 1; len <=
x.length() - i; len++)
{
// Storing the generated
// substring if it is
// absent in the map.
map[x.substr(i, len)] = true;
}
}
}
for (itr = map.begin(); itr != map.end();
++itr) {
// Printing all values in map.
cout << itr->first << '\n';
}
}
// Driver code
int main()
{
string str = "GeeksForGeeks";
generateVowelSubstrings(str);
return 0;
}
Java
/*package whatever //do not write package name here */
// Java code to implement above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to check if a character is vowel
public static boolean isVowel(String c)
{
// checking for vowels.
return (c.equals("a") || c.equals("A")
|| c.equals("e") || c.equals("E")
|| c.equals("i") || c.equals("I")
|| c.equals("o") || c.equals("O")
|| c.equals("u") || c.equals("U"));
}
// extracting all the maximum length sub-strings that
// contain only vowels.
public static HashMap<String, Boolean>
VowelSubstrings(String string)
{
String str = "";
// using map to remove identicals substrings. Ex :-
// AiotrfAiopdvge(it has 2 "Aio").
HashMap<String, Boolean> map = new HashMap<>();
for (int i = 0; i < string.length(); i++) {
String subStr = string.substring(i, (i + 1));
if (isVowel(subStr)) {
str += subStr;
}
else {
// storing a substring only if it is
// present.
if (!str.isEmpty())
map.putIfAbsent(str, true);
str = "";
}
}
if (!str.isEmpty())
map.putIfAbsent(str, true);
return map;
}
// Function to generate all unique substrings
// containing only vowels
public static void
generateVowelSubstrings(String string)
{
HashMap<String, Boolean> substringMap
= VowelSubstrings(string);
HashMap<String, Boolean> map = new HashMap<>();
for (String key : substringMap.keySet()) {
// for each key(substring) stored in map, we
// generate all possible substrings.
for (int i = 0; i < key.length(); i++) {
for (int j = i + 1; j <= key.length();
j++) {
// storing the generated substring if it
// is absent in the map.
map.putIfAbsent(key.substring(i, j),
true);
}
}
}
for (String key : map.keySet()) {
// printing all values in map.
System.out.println(key);
}
}
// Driver Code
public static void main(String[] args)
{
String str = "GeeksForGeeks";
generateVowelSubstrings(str);
}
}
Python3
# Python code to implement above approach # Function to check if a character is vowel def isVowel(c): # Checking for vowels. return ((c == "a") or (c == "A") or (c == "e") or (c == "E") or (c == "i") or (c == "I") or (c == "o") or (c == "O") or (c == "u") or (c == "U")) # Extracting all the maximum length # sub-Strings that contain only vowels. def vowelSubStrings(params): Str = "" # Using map to remove identicals # subStrings. e.g. AiotrfAio has 2 "Aio". map = dict() for i in range(len(params)): subString = params[i:i + 1] if (isVowel(subString)): Str += subString else: # Storing a subString only if # it is not empty. if (len(Str) > 0): map[Str] = True Str = "" if (len(Str) > 0): map[Str] = True return map # Function to generate all unique subStrings # containing only vowels def generateVowelSubStrings(params): subStringMap = vowelSubStrings(params) map = dict() # map iterator. for [key,val] in subStringMap.items(): x = key # For each subString stored in map # generate all possible subStrings. for i in range(len(x)): for Len in range(1,len(x) - i + 1): # Storing the generated # subString if it is # absent in the map. map[x[i: i+Len]] = True for [key,val] in map.items(): # Printing all values in map. print(key) # Driver code Str = "GeeksForGeeks" generateVowelSubStrings(Str) # This code is contributed by shinjanpatra
C#
/*package whatever //do not write package name here */
// C# code to implement the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to check if a character is vowel
public static bool isVowel(char ch)
{
return (ch == 'a' || ch == 'A' || ch == 'e'
|| ch == 'E' || ch == 'i' || ch == 'I'
|| ch == 'o' || ch == 'O' || ch == 'u'
|| ch == 'U');
}
// Function to check whether
// string contains only vowel
public static bool isValid(string s)
{
int n = s.Length;
for (int i = 0; i < n; i++)
{
// Check if the character is
// not vowel then invalid
if (!isVowel(s[i]))
return false;
}
return true;
}
// Function for generating unique substrings of vowels.
public static void generateVowelSubstrings(string str)
{
Dictionary<string, bool> map
= new Dictionary<string, bool>();
// Generate all subString of s
for (int i = 0; i < str.Length; i++) {
string temp = "";
for (int j = i; j < str.Length; j++) {
temp += str[j];
// If temp contains only vowels
if (isValid(temp)) {
// store it only if substring is absent
// in map.
if (!map.ContainsKey(temp))
map[temp] = true;
}
}
}
foreach(String i in map.Keys)
{
// printing all unique substring.
Console.WriteLine(i);
}
}
// Driver Code
public static void Main(string[] args)
{
string str = "GeeksForGeeks";
generateVowelSubstrings(str);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript code to implement above approach
// Function to check if a character is vowel
const isVowel = (c) => {
// Checking for vowels.
return ((c == "a") || (c == "A") ||
(c == "e") || (c == "E") ||
(c == "i") || (c == "I") ||
(c == "o") || (c == "O") ||
(c == "u") || (c == "U"));
}
// Extracting all the maximum length
// sub-strings that contain only vowels.
const vowelSubstrings = (params) => {
let str = "";
// Using map to remove identicals
// substrings. e.g. AiotrfAio has 2 "Aio".
let map = {};
for (let i = 0; i < params.length; i++) {
let subString = params.substring(i, i + 1);
if (isVowel(subString)) {
str += subString;
}
else {
// Storing a substring only if
// it is not empty.
if (str.length !== 0)
map[str] = true;
str = "";
}
}
if (str.length !== 0)
map[str] = true;
return map;
}
// Function to generate all unique substrings
// containing only vowels
const generateVowelSubstrings = (params) => {
let substringMap = vowelSubstrings(params);
let map = {};
// map iterator.
for (let itr in substringMap) {
let x = itr;
// For each substring stored in map
// generate all possible substrings.
for (let i = 0; i < x.length; i++)
{
for (let len = 1; len <= x.length - i; len++)
{
// Storing the generated
// substring if it is
// absent in the map.
map[x.substring(i, i + len)] = true;
}
}
}
for (let itr in map)
{
// Printing all values in map.
document.write(`${itr}<br/>`);
}
}
// Driver code
let str = "GeeksForGeeks";
generateVowelSubstrings(str);
// This code is contributed by rakeshsahni
</script>
Producción
o ee e
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)