Dada una string S que consta de N caracteres en minúscula, la tarea es encontrar la longitud de la substring más larga que consta de un número par de vocales .
Ejemplos:
Entrada: S= “bcbcbc”
Salida: 6
Explicación:
Considere la substring S[0, 5], es decir, “bcbcbc” es la substring más larga porque todas las vocales: a, e, i, o y u aparecen como 0 (que es par) numero de veces.Entrada: S = “ebbaa”
Salida: 4
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las substrings posibles a partir de la string S dada y, para cada substring, verificar si la frecuencia de todas las vocales en la substring es par o no . Si se encuentra que es verdadero , actualice la longitud máxima de la string requerida. Después de verificar todas las substrings, imprima la longitud máxima obtenida.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de Hashing . La idea es inicializar una string, digamos temp de tamaño 5 correspondiente a las 5 vocales (a, e, i, o, u) con todos 0 , donde s[i] = 0 indica que la i -ésima vocal está ocurriendo un par numero de veces. Ahora, recorra la string dada y encuentre el mismo estado de la string, la temperatura del mapa y actualice la longitud máxima. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como 0 que almacene el resultado requerido.
- Inicialice una string , digamos temp de tamaño 5 como «00000» .
- Cree un hashmap , M para almacenar el índice de aparición de la string temporal e inicialice el valor de temp en M como -1 .
- Recorra la string dada S sobre el rango [0, N – 1] usando la variable i y realice los siguientes pasos:
- Si el carácter S[i] es una vocal, actualice la string temp .
- Si la string temporal está presente en el mapa M , almacene su valor del mapa M en una variable X y actualice el valor de ans al máximo de ans y (i – X) .
- De lo contrario, actualice el valor de temp en el mapa M as i .
- Después de completar los pasos anteriores, imprima el valor de ans 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 the length of the
// longest substring having even number
// of vowels
int longestSubstring(string s)
{
// Create two hashmaps
unordered_map<string, int> indexes;
unordered_map<char, int> chars(
{ { 'a', 0 }, { 'e', 1 },
{ 'i', 2 }, { 'o', 3 },
{ 'u', 4 } });
// Keep the track of frequencies
// of the vowels
string evenOdd = "00000";
indexes[evenOdd] = -1;
// Stores the maximum length
int length = 0;
// Traverse the given string S
for (int i = 0; i < s.size(); ++i) {
char c = s[i];
// Find character in the map
auto it = chars.find(c);
// If it is a vowel, then update
// the frequency
if (it != chars.end()) {
evenOdd[it->second]
= evenOdd[it->second]
== '0'
? '1'
: '0';
}
// Find the index of occurrence
// of the string evenOdd in map
auto lastIndex = indexes.find(evenOdd);
if (lastIndex == indexes.end()) {
indexes[evenOdd] = i;
}
// Update the maximum length
else {
length = max(
length, i - lastIndex->second);
}
}
// Print the maximum length
cout << length;
}
// Driver Code
int main()
{
string S = "bcbcbc";
longestSubstring(S);
return 0;
}
Python3
# Python3 program for the above approach
# Function to find the length of the
# longest substring having even number
# of vowels
def longestSubstring(s):
# Create two hashmaps
indexes = {}
chars = {}
chars['a'] = 0
chars['e'] = 1
chars['i'] = 2
chars['o'] = 3
chars['u'] = 4
# Keep the track of frequencies
# of the vowels
evenOdd = "00000"
evenOdd = [i for i in evenOdd]
indexes["".join(evenOdd)] = -1
# Stores the maximum length
length = 0
# Traverse the given string S
for i in range(len(s)):
c = s[i]
# Find character in the map
# If it is a vowel, then update
# the frequency
if (c in chars):
evenOdd[chars[it]] = '1' if evenOdd[chars[it]] else '0'
# Find the index of occurrence
# of the string evenOdd in map
if ("".join(evenOdd) not in indexes):
indexes["".join(evenOdd)] = i
# Update the maximum length
else:
length = max(
length, i - indexes["".join(evenOdd)])
# Print the maximum length
print(length)
# Driver Code
if __name__ == '__main__':
S = "bcbcbc"
longestSubstring(S)
# This code is contributed by mohit kumar 29
Javascript
<script>
// JavaScript code for the approach
// Function to find the length of the
// longest substring having even number
// of vowels
function longestSubstring(s)
{
// Create two hashmaps
let indexes = new Map();
let chars = new Map();
chars.set('a',0);
chars.set('e',1);
chars.set('i',2);
chars.set('o',3);
chars.set('u',4);
// Keep the track of frequencies
// of the vowels
let evenOdd = "00000";
indexes.set(evenOdd , -1);
// Stores the maximum length
let length = 0;
// Traverse the given string S
for (let i = 0; i <br s.length; ++i) {
let c = s[i];
// If it is a vowel, then update
// the frequency
if (chars.has(c)) {
evenOdd.set(chars.get(c),(evenOdd.get(chars.get(c)) == '0')? '1': '0');
}
// Find the index of occurrence
// of the string evenOdd in map
if (indexes.has(evenOdd) == false) {
indexes.set(evenOdd,i);
}
// Update the maximum length
else {
length = Math.max(length, i - indexes.get(evenOdd));
}
}
// Print the maximum length
document.write(length,"</br>");
}
// Driver Code
let S = "bcbcbc";
longestSubstring(S);
// This code is contributed by shinjanpatra
</script>
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
// Function to find the length of the
// longest substring having even number
// of vowels
static void longestSubstring(String s)
{
// Create two hashmaps
HashMap<String, Integer> indexes = new HashMap<>();
HashMap<Character, Integer> chars = new HashMap<>(){{
put('a', 0);put('e', 1);
put('i', 2);put('o', 3);
put('u', 4);
}} ;
// Keep the track of frequencies
// of the vowels
String evenOdd = "00000";
indexes.put(evenOdd , -1);
// Stores the maximum length
int length = 0;
// Traverse the given string S
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
// Find character in the map
boolean it = chars.containsKey(c);
// If it is a vowel, then update
// the frequency
if (it != false) {
if(evenOdd.charAt(chars.get(c)) == '0'){
evenOdd = evenOdd.substring(0,chars.get(c)) + '1' + evenOdd.substring(chars.get(c)+1);
}
else{
evenOdd = evenOdd.substring(0,chars.get(c)) + '0' + evenOdd.substring(chars.get(c)+1);
}
}
// Find the index of occurrence
// of the string evenOdd in map
boolean lastIndex = indexes.containsKey(evenOdd);
if (lastIndex == false) {
indexes.put(evenOdd, i);
}
// Update the maximum length
else {
length = Math.max(length, i - indexes.get(evenOdd));
}
}
// Print the maximum length
System.out.println(length);
}
// Driver Code
public static void main(String args[])
{
// Given Input
String S = "bcbcbc";
longestSubstring(S);
}
}
// code is contributed by shinjanpatra
6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)