Dada la string str que consta solo de alfabetos ingleses en minúsculas, la tarea es encontrar la substring de menor longitud que contiene todas las vocales. Si no se encuentra tal substring, imprima -1 .
Ejemplo:
Entrada: str = “babeivoucu”
Salida: 7
Explicación: La substring más pequeña que contiene cada vocal al menos una vez es “abeivou” de longitud 7.Entrada: str = “abcdef”
Salida: -1
Explicación: No se encuentra tal substring.
- Almacene las frecuencias de cada vocal y los índices en los que están presentes las vocales.
- Si no están presentes todas las vocales, imprima inmediatamente -1.
- Tome dos punteros i y j en el primer y último índice que contiene una vocal.
- Si las frecuencias de las vocales en el i -ésimo y j -ésimo índice exceden 1, disminuya el conteo de esa vocal y cambie i y j a la derecha e izquierda respectivamente al siguiente índice que contenga una vocal.
- Si las frecuencias de las vocales en el índice i o j son iguales a 1, configure flag1 o flag2 respectivamente y continúe.
- Una vez que se establecen flag1 y flag2, la longitud de la substring no se puede minimizar más. La distancia entre los índices actuales señalados por los dos punteros denota el resultado.
El siguiente código es la implementación del enfoque anterior:
C++
// C++ Program to find the
// length of the smallest
// substring of which
// contains all vowels
#include <bits/stdc++.h>
using namespace std;
int findMinLength(string s)
{
int n = s.size();
// Map to store the
// frequency of vowels
map<char, int> counts;
// Store the indices
// which contains
// the vowels
vector<int> indices;
for (int i = 0; i < n; i++) {
if (s[i] == 'a' || s[i] == 'e'
|| s[i] == 'o'
|| s[i] == 'i'
|| s[i] == 'u') {
counts[s[i]]++;
indices.push_back(i);
}
}
// If all vowels are not
// present in the string
if (counts.size() < 5)
return -1;
int flag1 = 0, flag2 = 0;
int i = 0;
int j = indices.size() - 1;
while ((j - i) >= 4) {
// If the frequency of the
// vowel at i-th index
// exceeds 1
if (!flag1
&& counts[s[indices[i]]] > 1) {
// Decrease the frequency
// of that vowel
counts[s[indices[i]]]--;
// Move to the left
i++;
}
// Otherwise set flag1
else
flag1 = 1;
// If the frequency of the
// vowel at j-th index
// exceeds 1
if (!flag2
&& counts[s[indices[j]]] > 1) {
// Decrease the frequency
// of that vowel
counts[s[indices[j]]]--;
// Move to the right
j--;
}
// Otherwise set flag2
else
flag2 = 1;
// If both flag1 and flag2
// are set, break out of the
// loop as the substring
// length cannot be minimized
if (flag1 && flag2)
break;
}
// Return the length of the substring
return (indices[j] - indices[i] + 1);
}
int main()
{
string s = "aaeebbeaccaaoiuooooooooiuu";
cout << findMinLength(s);
return 0;
}
Java
// Java program to find the length of
// the smallest substring of which
// contains all vowels
import java.util.*;
class GFG{
public static int findMinLength(String s)
{
int n = s.length();
// Map to store the
// frequency of vowels
HashMap<Character,
Integer> counts = new HashMap<>();
// Store the indices
// which contains
// the vowels
Vector<Integer> indices = new Vector<Integer>();
for(int i = 0; i < n; i++)
{
if (s.charAt(i) == 'a' ||
s.charAt(i) == 'e' ||
s.charAt(i) == 'o' ||
s.charAt(i) == 'i' ||
s.charAt(i) == 'u')
{
if (counts.containsKey(s.charAt(i)))
{
counts.replace(s.charAt(i),
counts.get(s.charAt(i)) + 1);
}
else
{
counts.put(s.charAt(i), 1);
}
indices.add(i);
}
}
// If all vowels are not
// present in the string
if (counts.size() < 5)
return -1;
int flag1 = 0, flag2 = 0;
int i = 0;
int j = indices.size() - 1;
while ((j - i) >= 4)
{
// If the frequency of the
// vowel at i-th index
// exceeds 1
if (flag1 == 0 &&
counts.get(s.charAt(
indices.get(i))) > 1)
{
// Decrease the frequency
// of that vowel
counts.replace(s.charAt(indices.get(i)),
counts.get(s.charAt(indices.get(i))) - 1);
// Move to the left
i++;
}
// Otherwise set flag1
else
flag1 = 1;
// If the frequency of the
// vowel at j-th index
// exceeds 1
if (flag2 == 0 &&
counts.get(s.charAt(
indices.get(j))) > 1)
{
// Decrease the frequency
// of that vowel
counts.replace(s.charAt(indices.get(j)),
counts.get(s.charAt(indices.get(j))) - 1);
// Move to the right
j--;
}
// Otherwise set flag2
else
flag2 = 1;
// If both flag1 and flag2
// are set, break out of the
// loop as the substring
// length cannot be minimized
if (flag1 == 1 && flag2 == 1)
break;
}
// Return the length of the substring
return (indices.get(j) - indices.get(i) + 1);
}
// Driver Code
public static void main(String[] args)
{
String s = "aaeebbeaccaaoiuooooooooiuu";
System.out.print(findMinLength(s));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to find the # length of the smallest # substring of which # contains all vowels from collections import defaultdict def findMinLength(s): n = len(s) # Map to store the # frequency of vowels counts = defaultdict(int) # Store the indices # which contains # the vowels indices = [] for i in range(n): if (s[i] == 'a' or s[i] == 'e' or s[i] == 'o' or s[i] == 'i' or s[i] == 'u'): counts[s[i]] += 1 indices.append(i) # If all vowels are not # present in the string if len(counts) < 5: return -1 flag1 = 0 flag2 = 0 i = 0 j = len(indices) - 1 while (j - i) >= 4: # If the frequency of the # vowel at i-th index # exceeds 1 if (~flag1 and counts[s[indices[i]]] > 1): # Decrease the frequency # of that vowel counts[s[indices[i]]] -= 1 # Move to the left i += 1 # Otherwise set flag1 else: flag1 = 1 # If the frequency of the # vowel at j-th index # exceeds 1 if (~flag2 and counts[s[indices[j]]] > 1): # Decrease the frequency # of that vowel counts[s[indices[j]]] -= 1 # Move to the right j -= 1 # Otherwise set flag2 else: flag2 = 1 # If both flag1 and flag2 # are set, break out of the # loop as the substring # length cannot be minimized if (flag1 and flag2): break # Return the length of the substring return (indices[j] - indices[i] + 1) # Driver Code s = "aaeebbeaccaaoiuooooooooiuu" print(findMinLength(s)) # This code is contributed by # divyamohan123
C#
// C# program to find the length of
// the smallest substring of which
// contains all vowels
using System;
using System.Collections.Generic;
class GFG{
public static int findMinLength(String s)
{
int n = s.Length;
int i = 0;
// Map to store the
// frequency of vowels
Dictionary<char,
int> counts = new Dictionary<char,
int>();
// Store the indices
// which contains
// the vowels
List<int> indices = new List<int>();
for(i = 0; i < n; i++)
{
if (s[i] == 'a' ||
s[i] == 'e' ||
s[i] == 'o' ||
s[i] == 'i' ||
s[i] == 'u')
{
if (counts.ContainsKey(s[i]))
{
counts[s[i]] = counts[s[i]] + 1;
}
else
{
counts.Add(s[i], 1);
}
indices.Add(i);
}
}
// If all vowels are not
// present in the string
if (counts.Count < 5)
return -1;
int flag1 = 0, flag2 = 0;
i = 0;
int j = indices.Count - 1;
while ((j - i) >= 4)
{
// If the frequency of the
// vowel at i-th index
// exceeds 1
if (flag1 == 0 &&
counts[s[indices[i]]] > 1)
{
// Decrease the frequency
// of that vowel
counts[s[indices[i]]]=
counts[s[indices[i]]] - 1;
// Move to the left
i++;
}
// Otherwise set flag1
else
flag1 = 1;
// If the frequency of the
// vowel at j-th index
// exceeds 1
if (flag2 == 0 &&
counts[s[indices[j]]] > 1)
{
// Decrease the frequency
// of that vowel
counts[s[indices[j]]] =
counts[s[indices[j]]] - 1;
// Move to the right
j--;
}
// Otherwise set flag2
else
flag2 = 1;
// If both flag1 and flag2
// are set, break out of the
// loop as the substring
// length cannot be minimized
if (flag1 == 1 && flag2 == 1)
break;
}
// Return the length of the substring
return (indices[j] - indices[i] + 1);
}
// Driver Code
public static void Main(String[] args)
{
String s = "aaeebbeaccaaoiuooooooooiuu";
Console.Write(findMinLength(s));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program to find the
// length of the smallest
// substring of which
// contains all vowels
function findMinLength(s)
{
var n = s.length;
// Map to store the
// frequency of vowels
var counts = new Map();
// Store the indices
// which contains
// the vowels
var indices = [];
for (var i = 0; i < n; i++) {
if (s[i] == 'a' || s[i] == 'e'
|| s[i] == 'o'
|| s[i] == 'i'
|| s[i] == 'u') {
if(counts.has(s[i]))
counts.set(s[i], counts.get(s[i])+1)
else
counts.set(s[i], 1)
indices.push(i);
}
}
// If all vowels are not
// present in the string
if (counts.size < 5)
return -1;
var flag1 = 0, flag2 = 0;
var i = 0;
var j = indices.length - 1;
while ((j - i) >= 4) {
// If the frequency of the
// vowel at i-th index
// exceeds 1
if (!flag1
&& counts.get(s[indices[i]]) > 1) {
// Decrease the frequency
// of that vowel
if(counts.has(s[indices[i]]))
counts.set(s[indices[i]],
counts.get(s[indices[i]])-1)
// Move to the left
i++;
}
// Otherwise set flag1
else
flag1 = 1;
// If the frequency of the
// vowel at j-th index
// exceeds 1
if (!flag2
&& counts.get(s[indices[j]]) > 1) {
// Decrease the frequency
// of that vowel
if(counts.has(s[indices[j]]))
counts.set(s[indices[j]],
counts.get(s[indices[j]])-1)
// Move to the right
j--;
}
// Otherwise set flag2
else
flag2 = 1;
// If both flag1 and flag2
// are set, break out of the
// loop as the substring
// length cannot be minimized
if (flag1 && flag2)
break;
}
// Return the length of the substring
return (indices[j] - indices[i] + 1);
}
var s = "aaeebbeaccaaoiuooooooooiuu";
document.write( findMinLength(s));
</script>
Producción:
9
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque de ventana deslizante :
- Mantenga un conteo de array para almacenar la frecuencia de cada vocal.
- Mantenga una variable de inicio para almacenar el índice de inicio de la substring actual.
- Iterar sobre la string y hacer lo siguiente:
- Aumenta la frecuencia del carácter si es una vocal.
- Mueva el inicio lo más a la derecha posible con la condición de que el carácter del inicio no sea una vocal o sea una vocal con una frecuencia mayor que 1, lo que significa que ha aparecido anteriormente.
- Una vez que el inicio se mueve lo más lejos posible, verifique si todas las vocales están presentes en la substring entre el inicio y el índice actual.
- Siempre que se cumpla la condición anterior, actualice la longitud mínima de dicha substring obtenida
- Imprime la longitud mínima de la substring obtenida o imprime -1 si no se obtiene dicha substring
El siguiente código implementa el enfoque anterior:
C++
// C++ Program to find the
// length of the smallest
// substring of which
// contains all vowels
#include <bits/stdc++.h>
using namespace std;
// Function to return the
// index for respective
// vowels to increase their count
int get_index(char ch)
{
if (ch == 'a')
return 0;
else if (ch == 'e')
return 1;
else if (ch == 'i')
return 2;
else if (ch == 'o')
return 3;
else if (ch == 'u')
return 4;
// Returns -1 for consonants
else
return -1;
}
// Function to find the minimum length
int findMinLength(string s)
{
int n = s.size();
int ans = n + 1;
// Store the starting index
// of the current substring
int start = 0;
// Store the frequencies of vowels
int count[5] = { 0 };
for (int x = 0; x < n; x++) {
int idx = get_index(s[x]);
// If the current character
// is a vowel
if (idx != -1) {
// Increase its count
count[idx]++;
}
// Move start as much
// right as possible
int idx_start
= get_index(s[start]);
while (idx_start == -1
|| count[idx_start] > 1) {
if (idx_start != -1) {
count[idx_start]--;
}
start++;
if (start < n)
idx_start
= get_index(s[start]);
}
// Condition for valid substring
if (count[0] > 0 && count[1] > 0
&& count[2] > 0 && count[3] > 0
&& count[4] > 0) {
ans = min(ans, x - start + 1);
}
}
if (ans == n + 1)
return -1;
return ans;
}
// Driver code
int main()
{
string s = "aaeebbeaccaaoiuooooooooiuu";
cout << findMinLength(s);
return 0;
}
Java
// Java program to find the length
// of the smallest subString of
// which contains all vowels
import java.util.*;
class GFG{
// Function to return the
// index for respective
// vowels to increase their count
static int get_index(char ch)
{
if (ch == 'a')
return 0;
else if (ch == 'e')
return 1;
else if (ch == 'i')
return 2;
else if (ch == 'o')
return 3;
else if (ch == 'u')
return 4;
// Returns -1 for consonants
else
return -1;
}
// Function to find the minimum length
static int findMinLength(String s)
{
int n = s.length();
int ans = n + 1;
// Store the starting index
// of the current subString
int start = 0;
// Store the frequencies of vowels
int count[] = new int[5];
for(int x = 0; x < n; x++)
{
int idx = get_index(s.charAt(x));
// If the current character
// is a vowel
if (idx != -1)
{
// Increase its count
count[idx]++;
}
// Move start as much
// right as possible
int idx_start = get_index(s.charAt(start));
while (idx_start == -1 ||
count[idx_start] > 1)
{
if (idx_start != -1)
{
count[idx_start]--;
}
start++;
if (start < n)
idx_start = get_index(s.charAt(start));
}
// Condition for valid subString
if (count[0] > 0 && count[1] > 0 &&
count[2] > 0 && count[3] > 0 &&
count[4] > 0)
{
ans = Math.min(ans, x - start + 1);
}
}
if (ans == n + 1)
return -1;
return ans;
}
// Driver code
public static void main(String[] args)
{
String s = "aaeebbeaccaaoiuooooooooiuu";
System.out.print(findMinLength(s));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 Program to find the # length of the smallest # substring of which # contains all vowels # Function to return the # index for respective # vowels to increase their count def get_index(ch): if (ch == 'a'): return 0 elif (ch == 'e'): return 1 elif (ch == 'i'): return 2 elif (ch == 'o'): return 3 elif (ch == 'u'): return 4 # Returns -1 for consonants else: return -1 # Function to find the minimum length def findMinLength(s): n = len(s) ans = n + 1 # Store the starting index # of the current substring start = 0 # Store the frequencies # of vowels count = [0] * 5 for x in range (n): idx = get_index(s[x]) # If the current character # is a vowel if (idx != -1): # Increase its count count[idx] += 1 # Move start as much # right as possible idx_start = get_index(s[start]) while (idx_start == -1 or count[idx_start] > 1): if (idx_start != -1): count[idx_start] -= 1 start += 1 if (start < n): idx_start = get_index(s[start]) # Condition for valid substring if (count[0] > 0 and count[1] > 0 and count[2] > 0 and count[3] > 0 and count[4] > 0): ans = min(ans, x - start + 1) if (ans == n + 1): return -1 return ans # Driver code if __name__ == "__main__": s = "aaeebbeaccaaoiuooooooooiuu" print(findMinLength(s)) # This code is contributed by Chitranayal
C#
// C# program to find the length
// of the smallest subString of
// which contains all vowels
using System;
class GFG{
// Function to return the
// index for respective
// vowels to increase their count
static int get_index(char ch)
{
if (ch == 'a')
return 0;
else if (ch == 'e')
return 1;
else if (ch == 'i')
return 2;
else if (ch == 'o')
return 3;
else if (ch == 'u')
return 4;
// Returns -1 for consonants
else
return -1;
}
// Function to find the minimum length
static int findMinLength(String s)
{
int n = s.Length;
int ans = n + 1;
// Store the starting index
// of the current subString
int start = 0;
// Store the frequencies of vowels
int []count = new int[5];
for(int x = 0; x < n; x++)
{
int idx = get_index(s[x]);
// If the current character
// is a vowel
if (idx != -1)
{
// Increase its count
count[idx]++;
}
// Move start as much
// right as possible
int idx_start = get_index(s[start]);
while (idx_start == -1 ||
count[idx_start] > 1)
{
if (idx_start != -1)
{
count[idx_start]--;
}
start++;
if (start < n)
idx_start = get_index(s[start]);
}
// Condition for valid subString
if (count[0] > 0 && count[1] > 0 &&
count[2] > 0 && count[3] > 0 &&
count[4] > 0)
{
ans = Math.Min(ans, x - start + 1);
}
}
if (ans == n + 1)
return -1;
return ans;
}
// Driver code
public static void Main(String[] args)
{
String s = "aaeebbeaccaaoiuooooooooiuu";
Console.Write(findMinLength(s));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to find the length
// of the smallest subString of
// which contains all vowels
// Function to return the
// index for respective
// vowels to increase their count
function get_index(ch)
{
if (ch == 'a')
return 0;
else if (ch == 'e')
return 1;
else if (ch == 'i')
return 2;
else if (ch == 'o')
return 3;
else if (ch == 'u')
return 4;
// Returns -1 for consonants
else
return -1;
}
// Function to find the minimum length
function findMinLength(s)
{
let n = s.length;
let ans = n + 1;
// Store the starting index
// of the current subString
let start = 0;
// Store the frequencies of vowels
let count = new Array(5);
for(let i = 0; i < 5; i++)
{
count[i] = 0;
}
for(let x = 0; x < n; x++)
{
let idx = get_index(s[x]);
// If the current character
// is a vowel
if (idx != -1)
{
// Increase its count
count[idx]++;
}
// Move start as much
// right as possible
let idx_start = get_index(s[start]);
while (idx_start == -1 ||
count[idx_start] > 1)
{
if (idx_start != -1)
{
count[idx_start]--;
}
start++;
if (start < n)
idx_start = get_index(s[start]);
}
// Condition for valid subString
if (count[0] > 0 && count[1] > 0 &&
count[2] > 0 && count[3] > 0 &&
count[4] > 0)
{
ans = Math.min(ans, x - start + 1);
}
}
if (ans == n + 1)
return -1;
return ans;
}
// Driver code
let s = "aaeebbeaccaaoiuooooooooiuu";
document.write(findMinLength(s));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
9
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shobhitgupta907 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA