Dada una string s, tenemos que encontrar la longitud de la substring más larga de s que contiene exactamente K vocales distintas.
Nota: Considere los caracteres en mayúsculas y minúsculas como dos caracteres diferentes.
Ejemplos:
Entrada: s = “tHeracEBetwEEntheTwo”, k = 1
Salida: 14
Explicación: la substring más larga con solo 1 vocal es “cEBetwEEntheTw”
y su longitud es 14.
Entrada: s = “artyebui”, k = 2
Salida: 6
Explicación: la substring más larga con solo 2 vocales es “rtyebu”
Enfoque de fuerza bruta: para cada substring, verificamos los criterios para K vocal distinta y verificamos la longitud. Finalmente, la mayor longitud será el resultado.
Enfoque eficiente: aquí mantenemos el conteo de vocales que ocurren en la substring. Hasta que K no sea cero, contamos la vocal distinta que aparece en la substring. A medida que K se vuelve negativa, comenzamos a eliminar la primera vocal de la substring que hemos encontrado hasta ese momento, de modo que sea posible que una nueva substring (de mayor longitud) sea posible después. A medida que eliminamos la vocal, disminuimos su recuento para que la nueva substring pueda contener esa vocal que aparece en la última parte de la string. Y como K es 0 obtenemos la longitud de la substring.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find the longest substring
// with k distinct vowels.
#include <bits/stdc++.h>
using namespace std;
#define MAX 128
// Function to check whether a character is
// vowel or not
bool isVowel(char x)
{
return (x == 'a' || x == 'e' || x == 'i' ||
x == 'o' || x == 'u' || x == 'A' ||
x == 'E' || x == 'I' || x == 'O' ||
x == 'U');
}
int KDistinctVowel(char s[], int k)
{
// length of string
int n = strlen(s);
// array for count of characters
int c[MAX];
memset(c, 0, sizeof(c));
// Initialize result to be
// negative
int result = -1;
for (int i = 0, j = -1; i < n; ++i) {
int x = s[i];
// If letter is vowel then we
// increment its count value
// and decrease the k value so
// that if we again encounter the
// same vowel character then we
// don't consider it for our result
if (isVowel(x)) {
if (++c[x] == 1) {
// Decrementing the K value
--k;
}
}
// Till k is 0 above if condition run
// after that this while loop condition
// also become active. Here what we have
// done actually is that, if K is less
// than 0 then we eliminate the first
// vowel we have encountered till that
// time . Now K is incremented and k
// becomes 0. So, now we calculate the
// length of substring from the present
// index to the deleted index of vowel
// which result in our results.
while (k < 0) {
x = s[++j];
if (isVowel(x)) {
// decreasing the count
// so that it may appear
// in another substring
// appearing after this
// present substring
if (--c[x] == 0) {
// incrementing the K value
++k;
}
}
}
// Checking the maximum value
// of the result by comparing
// the length of substring
// whenever K value is 0 means
// K distinct vowel is present
// in substring
if (k == 0)
result = max(result, i - j);
}
return result;
}
// Driver code
int main(void)
{
char s[] = "tHeracEBetwEEntheTwo";
int k = 1;
cout << KDistinctVowel(s, k);
return 0;
}
Java
// Java program to find the longest substring
// with k distinct vowels.
class GFG {
static int MAX = 128;
// Function to check whether a character is
// vowel or not
static boolean isVowel(char x) {
return (x == 'a' || x == 'e' || x == 'i' ||
x == 'o' || x == 'u' || x == 'A' ||
x == 'E' || x == 'I' || x == 'O' ||
x == 'U');
}
static int KDistinctVowel(String s, int k) {
// length of string
int n = s.length();
// array for count of characters
int[] c = new int[MAX];
//Array.Clear(c, 0, c.Length);
// Initialize result to be
// negative
int result = -1;
for (int i = 0, j = -1; i < n; ++i) {
char x = s.charAt(i);
// If letter is vowel then we
// increment its count value
// and decrease the k value so
// that if we again encounter the
// same vowel character then we
// don't consider it for our result
if (isVowel(x)) {
if (++c[x] == 1) {
// Decrementing the K value
--k;
}
}
// Till k is 0 above if condition run
// after that this while loop condition
// also become active. Here what we have
// done actually is that, if K is less
// than 0 then we eliminate the first
// vowel we have encountered till that
// time . Now K is incremented and k
// becomes 0. So, now we calculate the
// length of substring from the present
// index to the deleted index of vowel
// which result in our results.
while (k < 0) {
x = s.charAt(++j);
if (isVowel(x)) {
// decreasing the count
// so that it may appear
// in another substring
// appearing after this
// present substring
if (--c[x] == 0) {
// incrementing the K value
++k;
}
}
}
// Checking the maximum value
// of the result by comparing
// the length of substring
// whenever K value is 0 means
// K distinct vowel is present
// in substring
if (k == 0) {
result = Math.max(result, i - j);
}
}
return result;
}
// Driver code
public static void main(String[] args) {
String s = "tHeracEBetwEEntheTwo";
int k = 1;
System.out.println(KDistinctVowel(s, k));
}
}
/* This Java code is contributed by Rajput-Ji*/
Python3
# Python3 program to find the longest substring # with k distinct vowels. MAX = 128 # Function to check whether a character is # vowel or not def isVowel(x): return (x == 'a' or x == 'e' or x == 'i' or x == 'o' or x == 'u' or x == 'A' or x == 'E' or x == 'I' or x == 'O' or x == 'U') def KDistinctVowel(c,k): n = len(s) c = [0 for i in range(MAX)] result = -1 j = -1 for i in range(n): x=s[i] # If letter is vowel then we # increment its count value # and decrease the k value so # that if we again encounter the # same vowel character then we # don't consider it for our result if isVowel(x): c[ord(x)] += 1 if c[ord(x)] == 1: k -= 1 # Till k is 0 above if condition run # after that this while loop condition # also become active. Here what we have # done actually is that, if K is less # than 0 then we eliminate the first # vowel we have encountered till that # time . Now K is incremented and k # becomes 0. So, now we calculate the # length of substring from the present # index to the deleted index of vowel # which result in our results. while k < 0: j += 1 x = s[j] if isVowel(x): # decreasing the count # so that it may appear # in another substring # appearing after this # present substring c[ord(x)] -= 1 k += 1 # Checking the maximum value # of the result by comparing # the length of substring # whenever K value is 0 means # K distinct vowel is present # in substring if k == 0: result = max(result, i - j) return result s = "tHeracEBetwEEntheTwo" k = 1 print(KDistinctVowel(s, k)) # This code is contributed by mohit kumar 29
C#
// C# program to find the longest substring
// with k distinct vowels.
using System;
class GFG {
static int MAX = 128;
// Function to check whether a character is
// vowel or not
static bool isVowel(char x)
{
return (x == 'a' || x == 'e' || x == 'i' ||
x == 'o' || x == 'u' || x == 'A' ||
x == 'E' || x == 'I' || x == 'O' ||
x == 'U');
}
static int KDistinctVowel(string s, int k)
{
// length of string
int n = s.Length;
// array for count of characters
int []c = new int[MAX];
Array.Clear(c, 0, c.Length);
// Initialize result to be
// negative
int result = -1;
for (int i = 0, j = -1; i < n; ++i) {
char x = s[i];
// If letter is vowel then we
// increment its count value
// and decrease the k value so
// that if we again encounter the
// same vowel character then we
// don't consider it for our result
if (isVowel(x)) {
if (++c[x] == 1) {
// Decrementing the K value
--k;
}
}
// Till k is 0 above if condition run
// after that this while loop condition
// also become active. Here what we have
// done actually is that, if K is less
// than 0 then we eliminate the first
// vowel we have encountered till that
// time . Now K is incremented and k
// becomes 0. So, now we calculate the
// length of substring from the present
// index to the deleted index of vowel
// which result in our results.
while (k < 0) {
x = s[++j];
if (isVowel(x)) {
// decreasing the count
// so that it may appear
// in another substring
// appearing after this
// present substring
if (--c[x] == 0) {
// incrementing the K value
++k;
}
}
}
// Checking the maximum value
// of the result by comparing
// the length of substring
// whenever K value is 0 means
// K distinct vowel is present
// in substring
if (k == 0) {
result = Math.Max(result, i - j);
}
}
return result;
}
// Driver code
static void Main()
{
string s = "tHeracEBetwEEntheTwo";
int k = 1;
Console.Write(KDistinctVowel(s, k));
}
}
// This code is contributed Manish Shaw
// (manishshaw1)
PHP
<?php
// PHP program to find the longest
// substring with k distinct vowels.
$MAX = 128;
// Function to check whether a
// character is vowel or not
function isVowel($x)
{
return ($x == 'a' || $x == 'e' || $x == 'i' ||
$x == 'o' || $x == 'u' || $x == 'A' ||
$x == 'E' || $x == 'I' || $x == 'O' ||
$x == 'U');
}
function KDistinctVowel($s, $k)
{
global $MAX;
// length of string
$n = strlen($s);
// array for count of characters
$c = array_fill(0, $MAX, NULL);
// Initialize result to be negative
$result = -1;
for ($i = 0, $j = -1; $i < $n; ++$i)
{
$x = $s[$i];
// If letter is vowel then we increment
// its count value and decrease the k
// value so that if we again encounter
// the same vowel character then we
// don't consider it for our result
if (isVowel($x))
{
if (++$c[ord($x)] == 1)
{
// Decrementing the K value
--$k;
}
}
// Till k is 0 above if condition run
// after that this while loop condition
// also become active. Here what we have
// done actually is that, if K is less
// than 0 then we eliminate the first
// vowel we have encountered till that
// time . Now K is incremented and k
// becomes 0. So, now we calculate the
// length of substring from the present
// index to the deleted index of vowel
// which result in our results.
while ($k < 0)
{
$x = $s[++$j];
if (isVowel($x))
{
// decreasing the count so that it
// may appear in another substring
// appearing after this present
// substring
if (--$c[ord($x)] == 0)
{
// incrementing the K value
++$k;
}
}
}
// Checking the maximum value of the
// result by comparing the length of
// substring whenever K value is 0
// means K distinct vowel is present
// in substring
if ($k == 0)
$result = max($result, $i - $j);
}
return $result;
}
// Driver code
$s = "tHeracEBetwEEntheTwo";
$k = 1;
echo KDistinctVowel($s, $k);
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to find the longest substring
// with k distinct vowels.
let MAX = 128;
// Function to check whether a character is
// vowel or not
function isVowel(x)
{
return (x == 'a' || x == 'e' || x == 'i' ||
x == 'o' || x == 'u' || x == 'A' ||
x == 'E' || x == 'I' || x == 'O' ||
x == 'U');
}
function KDistinctVowel(s,k)
{
// length of string
let n = s.length;
// array for count of characters
let c = new Array(MAX);
for(let i=0;i<c.length;i++)
{
c[i]=0;
}
//Array.Clear(c, 0, c.Length);
// Initialize result to be
// negative
let result = -1;
for (let i = 0, j = -1; i < n; ++i) {
let x = s[i];
// If letter is vowel then we
// increment its count value
// and decrease the k value so
// that if we again encounter the
// same vowel character then we
// don't consider it for our result
if (isVowel(x)) {
if (++c[x.charCodeAt(0)] == 1) {
// Decrementing the K value
--k;
}
}
// Till k is 0 above if condition run
// after that this while loop condition
// also become active. Here what we have
// done actually is that, if K is less
// than 0 then we eliminate the first
// vowel we have encountered till that
// time . Now K is incremented and k
// becomes 0. So, now we calculate the
// length of substring from the present
// index to the deleted index of vowel
// which result in our results.
while (k < 0) {
x = s[++j];
if (isVowel(x)) {
// decreasing the count
// so that it may appear
// in another substring
// appearing after this
// present substring
if (--c[x.charCodeAt(0)] == 0) {
// incrementing the K value
++k;
}
}
}
// Checking the maximum value
// of the result by comparing
// the length of substring
// whenever K value is 0 means
// K distinct vowel is present
// in substring
if (k == 0) {
result = Math.max(result, i - j);
}
}
return result;
}
// Driver code
let s = "tHeracEBetwEEntheTwo";
let k = 1;
document.write(KDistinctVowel(s, k));
// This code is contributed by rag2127
</script>
Producción:
7
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA