Dada la string str que contiene solo el alfabeto inglés en minúsculas y un número entero K , la tarea es encontrar una substring de longitud K que contenga el número máximo de vocales (es decir , ‘a’, ‘e’, ’i’, ‘o’, ‘u ‘ ). Si hay varias substrings de este tipo, devuelva la substring que sea lexicográficamente más pequeña.
Ejemplos:
Entrada: str = “geeksforgeeks”, K = 4
Salida: eeks
Explicación:
Las substrings con el número máximo de vocales son “geek”, “eeks”, que incluye 2 vocales. Pero «eeks» es lexicográficamente más pequeño.
Entrada: str = “ceebbaceeffo”, K = 3
Salida: ace
Explicación:
lexicográficamente, las substrings con el número máximo de vocales son “ace”.
Enfoque ingenuo:
para resolver el problema mencionado anteriormente, tenemos que generar todas las substrings de longitud K y almacenar lexicográficamente la más pequeña de todas las substrings que contengan el número máximo de vocales.
Complejidad temporal: O(N 2 )
Enfoque eficiente:
el procedimiento mencionado anteriormente se puede optimizar mediante la creación de una array de suma de prefijos pref[] de vocales donde el i-ésimo índice contiene el recuento de vocales desde 0 hasta el i-ésimo índice. El conteo de vocales para cualquier substring str[l : r] puede ser dado por pref[r]-pref[l-1] . Luego, encuentre la substring lexicográficamente más pequeña con el número máximo de vocales.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find
// lexicographically smallest
// K-length substring containing
// maximum number of vowels
#include <bits/stdc++.h>
using namespace std;
// Function that prints the
// lexicographically smallest
// K-length substring containing
// maximum number of vowels
string maxVowelSubString(
string str, int K)
{
// Store the length of the string
int N = str.length();
// Initialize a prefix sum array
int pref[N];
// Loop through the string to
// create the prefix sum array
for (int i = 0; i < N; i++) {
// Store 1 at the index
// if it is a vowel
if (str[i] == 'a'
or str[i] == 'e'
or str[i] == 'i'
or str[i] == 'o'
or str[i] == 'u')
pref[i] = 1;
// Otherwise, store 0
else
pref[i] = 0;
// Process the prefix array
if (i)
pref[i] += pref[i - 1];
}
// Initialize the variable to store
// maximum count of vowels
int maxCount = pref[K - 1];
// Initialize the variable
// to store substring
// with maximum count of vowels
string res = str.substr(0, K);
// Loop through the prefix array
for (int i = K; i < N; i++) {
// Store the current
// count of vowels
int currCount
= pref[i]
- pref[i - K];
// Update the result if current count
// is greater than maximum count
if (currCount > maxCount) {
maxCount = currCount;
res = str.substr(i - K + 1, K);
}
// Update lexicographically smallest
// substring if the current count
// is equal to the maximum count
else if (currCount == maxCount) {
string temp
= str.substr(
i - K + 1, K);
if (temp < res)
res = temp;
}
}
// Return the result
return res;
}
// Driver Program
int main()
{
string str = "ceebbaceeffo";
int K = 3;
cout << maxVowelSubString(str, K);
return 0;
}
Java
// Java program to find
// lexicographically smallest
// K-length substring containing
// maximum number of vowels
class GFG{
// Function that prints the
// lexicographically smallest
// K-length substring containing
// maximum number of vowels
static String maxVowelSubString(String str,
int K)
{
// Store the length of the string
int N = str.length();
// Initialize a prefix sum array
int []pref = new int[N];
// Loop through the string to
// create the prefix sum array
for (int i = 0; i < N; i++)
{
// Store 1 at the index
// if it is a vowel
if (str.charAt(i) == 'a' ||
str.charAt(i) == 'e' ||
str.charAt(i) == 'i' ||
str.charAt(i) == 'o' ||
str.charAt(i) == 'u')
pref[i] = 1;
// Otherwise, store 0
else
pref[i] = 0;
// Process the prefix array
if (i != 0)
pref[i] += pref[i - 1];
}
// Initialize the variable to store
// maximum count of vowels
int maxCount = pref[K - 1];
// Initialize the variable
// to store substring
// with maximum count of vowels
String res = str.substring(0, K);
// Loop through the prefix array
for (int i = K; i < N; i++)
{
// Store the current
// count of vowels
int currCount = pref[i] -
pref[i - K];
// Update the result if current count
// is greater than maximum count
if (currCount > maxCount)
{
maxCount = currCount;
res = str.substring(i - K + 1,
i + 1);
}
// Update lexicographically smallest
// substring if the current count
// is equal to the maximum count
else if (currCount == maxCount)
{
String temp = str.substring(i - K + 1,
i + 1);
if (temp.compareTo(res) < 0)
res = temp;
}
}
// Return the result
return res;
}
// Driver Code
public static void main(String []args)
{
String str = "ceebbaceeffo";
int K = 3;
System.out.print(maxVowelSubString(str, K));
}
}
// This code is contributed by Chitranayal
Python3
# Python3 program to find # lexicographically smallest # K-length substring containing # maximum number of vowels # Function that prints the # lexicographically smallest # K-length substring containing # maximum number of vowels def maxVowelSubString(str1, K): # Store the length of the string N = len(str1) # Initialize a prefix sum array pref = [0 for i in range(N)] # Loop through the string to # create the prefix sum array for i in range(N): # Store 1 at the index # if it is a vowel if (str1[i] == 'a' or str1[i] == 'e' or str1[i] == 'i' or str1[i] == 'o' or str1[i] == 'u'): pref[i] = 1 # Otherwise, store 0 else: pref[i] = 0 # Process the prefix array if (i): pref[i] += pref[i - 1] # Initialize the variable to # store maximum count of vowels maxCount = pref[K - 1] # Initialize the variable # to store substring with # maximum count of vowels res = str1[0:K] # Loop through the prefix array for i in range(K, N): # Store the current # count of vowels currCount = pref[i] - pref[i - K] # Update the result if current count # is greater than maximum count if (currCount > maxCount): maxCount = currCount res = str1[i - K + 1 : i + 1] # Update lexicographically smallest # substring if the current count # is equal to the maximum count elif (currCount == maxCount): temp = str1[i - K + 1 : i + 1] if (temp < res): res = temp # Return the result return res # Driver code if __name__ == '__main__': str1 = "ceebbaceeffo" K = 3 print(maxVowelSubString(str1, K)) # This code is contributed by Surendra_Gangwar
C#
// C# program to find
// lexicographically smallest
// K-length substring containing
// maximum number of vowels
using System;
class GFG{
// Function that prints the
// lexicographically smallest
// K-length substring containing
// maximum number of vowels
static string maxVowelSubString(string str,
int K)
{
// Store the length of the string
int N = str.Length;
// Initialize a prefix sum array
int []pref = new int[N];
// Loop through the string to
// create the prefix sum array
for (int i = 0; i < N; i++)
{
// Store 1 at the index
// if it is a vowel
if (str[i] == 'a' ||
str[i] == 'e' ||
str[i] == 'i' ||
str[i] == 'o' ||
str[i] == 'u')
pref[i] = 1;
// Otherwise, store 0
else
pref[i] = 0;
// Process the prefix array
if (i != 0)
pref[i] += pref[i - 1];
}
// Initialize the variable to store
// maximum count of vowels
int maxCount = pref[K - 1];
// Initialize the variable
// to store substring
// with maximum count of vowels
string res = str.Substring(0, K);
// Loop through the prefix array
for (int i = K; i < N; i++)
{
// Store the current
// count of vowels
int currCount = pref[i] -
pref[i - K];
// Update the result if current count
// is greater than maximum count
if (currCount > maxCount)
{
maxCount = currCount;
res = str.Substring(i - K + 1, K);
}
// Update lexicographically smallest
// substring if the current count
// is equal to the maximum count
else if (currCount == maxCount)
{
string temp = str.Substring(i - K + 1, K);
if (string.Compare(temp, res) == -1)
res = temp;
}
}
// Return the result
return res;
}
// Driver Code
public static void Main()
{
string str = "ceebbaceeffo";
int K = 3;
Console.Write(maxVowelSubString(str, K));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript program to find
// lexicographically smallest
// K-length substring containing
// maximum number of vowels
// Function that prints the
// lexicographically smallest
// K-length substring containing
// maximum number of vowels
function maxVowelSubString(str, K)
{
// St||e the length of the string
var N = str.length;
// Initialize a prefix sum array
var pref = Array(N);
// Loop through the string to
// create the prefix sum array
for(var i = 0; i < N; i++) {
// St||e 1 at the index
// if it is a vowel
if (str[i] == 'a'
|| str[i] == 'e'
|| str[i] == 'i'
|| str[i] == 'o'
|| str[i] == 'u')
pref[i] = 1;
// Otherwise, st||e 0
else
pref[i] = 0;
// Process the prefix array
if (i)
pref[i] += pref[i - 1];
}
// Initialize the variable to st||e
// maximum count of vowels
var maxCount = pref[K - 1];
// Initialize the variable
// to st||e substring
// with maximum count of vowels
var res = str.substring(0, K);
// Loop through the prefix array
for (var i = K; i < N; i++) {
// St||e the current
// count of vowels
var currCount
= pref[i]
- pref[i - K];
// Update the result if current count
// is greater than maximum count
if (currCount > maxCount) {
maxCount = currCount;
res = str.substring(i - K + 1, i - 1);
}
// Update lexicographically smallest
// substring if the current count
// is equal to the maximum count
else if (currCount == maxCount) {
var temp
= str.substring(
i - K + 1, i + 1);
if (temp < res)
res = temp;
}
}
// Return the result
return res;
}
// Driver Program
var str = "ceebbaceeffo";
var K = 3;
document.write( maxVowelSubString(str, K));
</script>
Producción
ace
Complejidad de tiempo: O(N)
Enfoque de espacio optimizado:
En lugar de almacenar sumas de prefijos, podemos usar una ventana deslizante y actualizar nuestro resultado en cada máximo.
C++
#include <iostream>
using namespace std;
// Helper function to check if a character is a vowel
bool isVowel(char c)
{
return c == 'a' or c == 'e' or c == 'i' or c == 'o'
or c == 'u';
}
// Function to find the maximum vowel substring
string maxVowelSubstring(string s, int k)
{
int maxCount = 0; // initialize maxCount as 0
string res = s.substr(
0, k); // and result as first substring of size k
for (int i = 0, count = 0; i < s.size();
i++) // iterate through the string
{
if (isVowel(
s[i])) // if current character is a vowel
count++; // then increase count
if (i >= k
and isVowel(
s[i - k])) // if character that is leaving
// the window is a vowel
count--; // then decrease count
if (count > maxCount) // if we get a substring
// having more vowels
{
maxCount = count; // update count
if (i >= k)
res = s.substr(i - k + 1,
k); // and update result
}
if (count == maxCount
and i >= k) // if we get a substring with same
// maximum number of vowels
{
string t = s.substr(i - k + 1, k);
if (t < res) // then check if it is
// lexicographically smaller than
// current result and update it
res = t;
}
}
return res;
}
// Driver code
int main()
{
string str = "geeksforgeeks";
int k = 4;
cout << maxVowelSubstring(str, k);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
static boolean isVowel(char c){
return c == 'a' || c == 'e' || c == 'i' || c == 'o'
|| c == 'u';
}
// Function to find the maximum vowel subString
static String maxVowelSubString(String s, int k)
{
int maxCount = 0; // initialize maxCount as 0
String res = s.substring(0, k); // and result as first subString of size k
for (int i = 0, count = 0; i < s.length();i++) // iterate through the String
{
if (isVowel(s.charAt(i))) // if current character is a vowel
count++; // then increase count
if (i >= k && isVowel(s.charAt(i - k))) // if character that is leaving
// the window is a vowel
count--; // then decrease count
if (count > maxCount) // if we get a subString
// having more vowels
{
maxCount = count; // update count
if (i >= k)
res = s.substring(i - k + 1,i + 1); // and update result
}
if (count == maxCount && i >= k) // if we get a subString with same
// maximum number of vowels
{
String t = s.substring(i - k + 1, i + 1);
if (t.compareTo(res) < 0){ // then check if it is
// lexicographically smaller than
// current result and update it
res = t;
}
}
}
return res;
}
public static void main (String[] args) {
String str = "geeksforgeeks";
int k = 4;
System.out.println(maxVowelSubString(str, k));
}
}
// This code is contributed by shinjanpatra.
Python3
# Helper function to check if a character is a vowel def isVowel(c): return (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u') # Function to find the maximum vowel substring def maxVowelSubstring(s, k): # initialize maxCount as 0 maxCount = 0 # and result as first substring of size k res = s[0:k] # iterate through the string count = 0 for i in range(len(s)): # if current character is a vowel if (isVowel(s[i])): count += 1 # then increase count # if character that is leaving if (i >= k and isVowel(s[i - k])): # the window is a vowel count -= 1 # then decrease count if (count > maxCount): # if we get a substring # having more vowels maxCount = count # update count if (i >= k): # and update result res = s[i - k + 1: i + 1] # if we get a substring with same if (count == maxCount and i >= k): # maximum number of vowels t = s[i - k + 1: i+1] if (t < res): # then check if it is # lexicographically smaller than # current result and update it res = t return res # driver code str = "geeksforgeeks" k = 4 print(maxVowelSubstring(str, k)) # This code is contributed by shinjanpatra
Javascript
<script>
// Helper function to check if a character is a vowel
function isVowel(c)
{
return (c == 'a' || c == 'e' || c == 'i' || c == 'o'
|| c == 'u');
}
// Function to find the maximum vowel substring
function maxVowelSubstring(s, k)
{
// initialize maxCount as 0
let maxCount = 0;
// and result as first substring of size k
let res = s.substr(0, k);
// iterate through the string
for (let i = 0, count = 0; i < s.length; i++)
{
// if current character is a vowel
if (isVowel(s[i]))
count++; // then increase count
// if character that is leaving
if (i >= k && isVowel(s[i - k]))
// the window is a vowel
count--; // then decrease count
if (count > maxCount) // if we get a substring
// having more vowels
{
maxCount = count; // update count
if (i >= k)
// and update result
res = s.substr(i - k + 1, k);
}
// if we get a substring with same
if (count == maxCount && i >= k)
// maximum number of vowels
{
let t = s.substr(i - k + 1, k);
if (t < res) // then check if it is
// lexicographically smaller than
// current result and update it
res = t;
}
}
return res;
}
let str = "geeksforgeeks";
let k = 4;
document.write(maxVowelSubstring(str, k));
</script>
Producción
eeks
Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA