Dada una string S de tamaño N que consiste en letras minúsculas, la tarea es imprimir la longitud de la substring más larga que consiste solo en vocales ordenadas en orden no creciente.
Ejemplos:
Entrada: S = “ueiaoaeiouuoiea”
Salida: 6
Explicación: La única substring que consta solo de vocales en orden no creciente es la substring {S[9], S[15]}, que es “uuoiea”.Entrada: S = “uuuioea”
Salida: 0
Enfoque: el problema dado se puede resolver usando HashSet . Siga los pasos a continuación para resolver el problema:
- Almacene todas las vocales en una array, digamos ch[] , en orden decreciente.
- Inicialice tres variables res, j y cuente como 0 para almacenar la longitud más larga de la substring requerida, para iterar sobre todas las vocales y para almacenar la longitud de la substring actual que satisfaga las condiciones respectivamente.
- Además, inicialice un HashSet , digamos mp , para almacenar todos los caracteres distintos de la substring actual que satisfagan las condiciones.
- Itere sobre los caracteres de la string S usando una variable i y realice las siguientes operaciones:
- Si S[i] es igual a ch[j] , agregue S[i] a mp y luego incremente j y cuente de 1 en 1 . Si el tamaño de mp es igual a 5 , actualice res a un máximo de res y cuente .
- De lo contrario, si j + 1 es menor que 5 y S[i] es igual a ch[j + 1] , entonces incremente j y cuente de 1 en 1 y agregue S[i] a mp . Si el tamaño de mp es igual a 5 , actualice res a un máximo de res y cuente .
- De lo contrario, si S[i] es igual a ‘ u ‘, entonces asigne 0 a j y 1 para contar y sume S[i] a mp . De lo contrario, asigne 0 tanto a j como a count .
- Después de completar los pasos anteriores, imprima el valor de res como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find length of the
// longest substring consisting only
// of vowels in non-increasing order
int count(string S, int N)
{
// Stores all vowels in decreasing order
char ch[] = { 'u', 'o', 'i', 'e', 'a' };
// Stores current index of array ch[]
int j = 0;
// Stores the result
int res = 0;
// Stores the count
// of current substring
int count = 0;
// Declare a HashSet to store the vowels
unordered_set<char> mp;
// Traverse the string, S
for(int i = 0; i < N; ++i)
{
// If S[i] is equal to ch[j]
if (S[i] == ch[j])
{
// Increment count by 1
++count;
// Add S[i] in the mp
mp.insert(S[i]);
// If length of mp is 5, update res
if (mp.size() == 5)
{
res = max(res, count);
}
}
// Else if j+1 is less than 5 and
// S[i] is equal to ch[j+1]
else if (j + 1 < 5 && S[i] == ch[j + 1])
{
// Add the S[i] in the mp
mp.insert(S[i]);
// Increment count by 1
++count;
// Increment j by 1
j++;
// If length of mp is 5, update res
if (mp.size() == 5)
{
res = max(res, count);
}
}
else
{
// Clear the mp
mp.clear();
// If S[i] is 'u'
if (S[i] == 'u')
{
// Add S[i] in the mp
mp.insert('u');
// Update j and assign 1 to count
j = 0;
count = 1;
}
// Else assign 0 to j and count
else
{
j = 0;
count = 0;
}
}
}
// Return the result
return res;
}
// Driver Code
int main()
{
string S = "ueiaoaeiouuoiea";
int N = S.size();
// Function Call
cout << count(S, N);
return 0;
}
// This code is contributed by Kingash
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find length of the
// longest substring consisting only
// of vowels in non-increasing order
static int count(String S, int N)
{
// Stores all vowels in decreasing order
char ch[] = { 'u', 'o', 'i', 'e', 'a' };
// Stores current index of array ch[]
int j = 0;
// Stores the result
int res = 0;
// Stores the count
// of current substring
int count = 0;
// Declare a HashSet to store the vowels
HashSet<Character> mp = new HashSet<>();
// Traverse the string, S
for (int i = 0; i < N; ++i) {
// If S[i] is equal to ch[j]
if (S.charAt(i) == ch[j]) {
// Increment count by 1
++count;
// Add S[i] in the mp
mp.add(S.charAt(i));
// If length of mp is 5, update res
if (mp.size() == 5) {
res = Math.max(res, count);
}
}
// Else if j+1 is less than 5 and
// S[i] is equal to ch[j+1]
else if (j + 1 < 5
&& S.charAt(i) == ch[j + 1]) {
// Add the S[i] in the mp
mp.add(S.charAt(i));
// Increment count by 1
++count;
// Increment j by 1
j++;
// If length of mp is 5, update res
if (mp.size() == 5) {
res = Math.max(res, count);
}
}
else {
// Clear the mp
mp.clear();
// If S[i] is 'u'
if (S.charAt(i) == 'u') {
// Add S[i] in the mp
mp.add('u');
// Update j and assign 1 to count
j = 0;
count = 1;
}
// Else assign 0 to j and count
else {
j = 0;
count = 0;
}
}
}
// Return the result
return res;
}
// Driver Code
public static void main(String[] args)
{
// Given Input
String S = "ueiaoaeiouuoiea";
int N = S.length();
// Function Call
System.out.println(count(S, N));
}
}
Python3
# Python3 program for the above approach
# Function to find length of the
# longest substring consisting only
# of vowels in non-increasing order
def count1(S, N):
# Stores all vowels in decreasing order
ch = ['u', 'o', 'i', 'e', 'a']
# Stores current index of array ch[]
j = 0
# Stores the result
res = 0
# Stores the count
# of current substring
count = 0;
# Declare a HashSet to store the vowels
mp = set()
# Traverse the string, S
for i in range(N):
# If S[i] is equal to ch[j]
if (S[i] == ch[j]):
# Increment count by 1
count += 1
# Add S[i] in the mp
mp.add(S[i])
# If length of mp is 5, update res
if (len(mp) == 5):
res = max(res, count)
# Else if j+1 is less than 5 and
# S[i] is equal to ch[j+1]
elif (j + 1 < 5 and S[i] == ch[j + 1]):
# Add the S[i] in the mp
mp.add(S[i])
# Increment count by 1
count += 1
# Increment j by 1
j += 1
# If length of mp is 5, update res
if (len(mp) == 5):
res = max(res, count)
else:
# Clear the mp
mp.clear()
# If S[i] is 'u'
if (S[i] == 'u'):
# Add S[i] in the mp
mp.add('u')
# Update j and assign 1 to count
j = 0
count = 1
# Else assign 0 to j and count
else:
j = 0
count = 0
# Return the result
return res
# Driver Code
if __name__ == '__main__':
S = "ueiaoaeiouuoiea"
N = len(S)
# Function Call
print(count1(S, N))
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find length of the
// longest substring consisting only
// of vowels in non-increasing order
static int count(string S, int N)
{
// Stores all vowels in decreasing order
char[] ch = { 'u', 'o', 'i', 'e', 'a' };
// Stores current index of array ch[]
int j = 0;
// Stores the result
int res = 0;
// Stores the count
// of current substring
int count = 0;
// Declare a HashSet to store the vowels
HashSet<char> mp = new HashSet<char>();
// Traverse the string, S
for (int i = 0; i < N; ++i) {
// If S[i] is equal to ch[j]
if (S[i] == ch[j]) {
// Increment count by 1
++count;
// Add S[i] in the mp
mp.Add(S[i]);
// If length of mp is 5, update res
if (mp.Count == 5) {
res = Math.Max(res, count);
}
}
// Else if j+1 is less than 5 and
// S[i] is equal to ch[j+1]
else if (j + 1 < 5 && S[i] == ch[j + 1]) {
// Add the S[i] in the mp
mp.Add(S[i]);
// Increment count by 1
++count;
// Increment j by 1
j++;
// If length of mp is 5, update res
if (mp.Count == 5) {
res = Math.Max(res, count);
}
}
else {
// Clear the mp
mp.Clear();
// If S[i] is 'u'
if (S[i] == 'u') {
// Add S[i] in the mp
mp.Add('u');
// Update j and assign 1 to count
j = 0;
count = 1;
}
// Else assign 0 to j and count
else {
j = 0;
count = 0;
}
}
}
// Return the result
return res;
}
// Driver Code
public static void Main(string[] args)
{
// Given Input
string S = "ueiaoaeiouuoiea";
int N = S.Length;
// Function Call
Console.WriteLine(count(S, N));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to find length of the
// longest substring consisting only
// of vowels in non-increasing order
function count(S, N)
{
// Stores all vowels in decreasing order
let ch = [ 'u', 'o', 'i', 'e', 'a' ];
// Stores current index of array ch[]
let j = 0;
// Stores the result
let res = 0;
// Stores the count
// of current substring
let count = 0;
// Declare a HashSet to store the vowels
let mp = new Map();
// Traverse the string, S
for(let i = 0; i < N; ++i)
{
// If S[i] is equal to ch[j]
if (S[i] == ch[j])
{
// Increment count by 1
++count;
// Add S[i] in the mp
mp.set(S[i], "");
// If length of mp is 5, update res
if (mp.size == 5)
{
res = Math.max(res, count);
}
}
// Else if j+1 is less than 5 and
// S[i] is equal to ch[j+1]
else if (j + 1 < 5 && S[i] == ch[j + 1])
{
// Add the S[i] in the mp
mp.set(S[i], "");
// Increment count by 1
++count;
// Increment j by 1
j++;
// If length of mp is 5, update res
if (mp.size == 5)
{
res = Math.max(res, count);
}
}
else
{
// Clear the mp
mp.clear();
// If S[i] is 'u'
if (S[i] == 'u')
{
// Add S[i] in the mp
mp.set('u', "");
// Update j and assign 1 to count
j = 0;
count = 1;
}
// Else assign 0 to j and count
else
{
j = 0;
count = 0;
}
}
}
// Return the result
return res;
}
// Driver Code
let S = "ueiaoaeiouuoiea";
let N = S.length;
// Function Call
document.write(count(S, N));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA