Dada una string S que consta de letras inglesas minúsculas, la tarea es encontrar la longitud de la substring más larga de la string dada, que tenga el mismo número de vocales y consonantes.
Ejemplos:
Entrada: S = “geeksforgeeks”
Salida: 10
Explicación:
La substring “eeksforgee” consta de 5 vocales y 5 consonantes. Los caracteres restantes son solo consonantes. Por lo tanto, cualquier substring más larga no tendrá el mismo número de vocales y consonantes.Entrada: S = “qwertyuiop”
Salida: 8
Explicación:
La substring “wertyuio” consta de 4 vocales y 4 consonantes.
Enfoque ingenuo: la solución más simple es generar todas las substrings de la string dada y, para cada substring, verificar si el recuento de vocales y consonantes es igual o no. Finalmente, imprima la longitud máxima de substring obtenida teniendo igual número de vocales y consonantes.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea es considerar una array de longitudes iguales a la de la string dada, almacenar 1 y -1 correspondientes a vocales y consonantes respectivamente, e imprimir la longitud de la sub-array más larga con la suma igual a 0 usando HashMap .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the length of
// the longest substring having equal
// number of vowel and consonant
int maxsubstringLength(string S, int N)
{
int arr[N];
// Generate the array
for (int i = 0; i < N; i++)
if (S[i] == 'a' || S[i] == 'e' || S[i] == 'i'
|| S[i] == 'o' || S[i] == 'u')
arr[i] = 1;
else
arr[i] = -1;
// Initialize variable
// to store result
int maxLen = 0;
// Stores the sum of subarray
int curr_sum = 0;
// Map to store indices of the sum
unordered_map<int, int> hash;
// Loop through the array
for (int i = 0; i < N; i++) {
curr_sum += arr[i];
// If sum is 0
if (curr_sum == 0)
// Count of vowels and consonants
// are equal
maxLen = max(maxLen, i + 1);
// Update the maximum length
// of substring in HashMap
if (hash.find(curr_sum) != hash.end())
maxLen = max(maxLen, i - hash[curr_sum]);
// Store the index of the sum
else
hash[curr_sum] = i;
}
// Return the maximum
// length of required substring
return maxLen;
}
// Driver Code
int main()
{
string S = "geeksforgeeks";
int n = sizeof(S) / sizeof(S[0]);
cout << maxsubstringLength(S, n);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to return the length of
// the longest subString having equal
// number of vowel and consonant
static int maxsubStringLength(char[] S, int N)
{
int arr[] = new int[N];
// Generate the array
for(int i = 0; i < N; i++)
if (S[i] == 'a' || S[i] == 'e' ||
S[i] == 'i' || S[i] == 'o' ||
S[i] == 'u')
arr[i] = 1;
else
arr[i] = -1;
// Initialize variable
// to store result
int maxLen = 0;
// Stores the sum of subarray
int curr_sum = 0;
// Map to store indices of the sum
HashMap<Integer, Integer> hash = new HashMap<>();
// Loop through the array
for(int i = 0; i < N; i++)
{
curr_sum += arr[i];
// If sum is 0
if (curr_sum == 0)
// Count of vowels and consonants
// are equal
maxLen = Math.max(maxLen, i + 1);
// Update the maximum length
// of subString in HashMap
if (hash.containsKey(curr_sum))
maxLen = Math.max(maxLen,
i - hash.get(curr_sum));
// Store the index of the sum
else
// hash[curr_sum] = i;
hash.put(curr_sum, i);
}
// Return the maximum
// length of required subString
return maxLen;
}
// Driver Code
public static void main(String[] args)
{
String S = "geeksforgeeks";
int n = S.length();
System.out.print(
maxsubStringLength(S.toCharArray(), n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to implement
# the above approach
# Function to return the length of
# the longest substring having equal
# number of vowel and consonant
def maxsubstringLength(S, N):
arr = [0] * N
# Generate the array
for i in range(N):
if(S[i] == 'a' or S[i] == 'e' or
S[i] == 'i' or S[i] == 'o' or
S[i] == 'u'):
arr[i] = 1
else:
arr[i] = -1
# Initialize variable
# to store result
maxLen = 0
# Stores the sum of subarray
curr_sum = 0
# Map to store indices of the sum
hash = {}
# Loop through the array
for i in range(N):
curr_sum += arr[i]
# If sum is 0
if(curr_sum == 0):
# Count of vowels and consonants
# are equal
maxLen = max(maxLen, i + 1)
# Update the maximum length
# of substring in HashMap
if(curr_sum in hash.keys()):
maxLen = max(maxLen, i - hash[curr_sum])
# Store the index of the sum
else:
hash[curr_sum] = i
# Return the maximum
# length of required substring
return maxLen
# Driver Code
S = "geeksforgeeks"
n = len(S)
# Function call
print(maxsubstringLength(S, n))
# This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return the length of
// the longest subString having equal
// number of vowel and consonant
static int maxsubStringLength(char[] S, int N)
{
int []arr = new int[N];
// Generate the array
for(int i = 0; i < N; i++)
if (S[i] == 'a' || S[i] == 'e' ||
S[i] == 'i' || S[i] == 'o' ||
S[i] == 'u')
arr[i] = 1;
else
arr[i] = -1;
// Initialize variable
// to store result
int maxLen = 0;
// Stores the sum of subarray
int curr_sum = 0;
// Map to store indices of the sum
Dictionary<int,
int> hash = new Dictionary<int,
int>();
// Loop through the array
for(int i = 0; i < N; i++)
{
curr_sum += arr[i];
// If sum is 0
if (curr_sum == 0)
// Count of vowels and consonants
// are equal
maxLen = Math.Max(maxLen, i + 1);
// Update the maximum length
// of subString in Dictionary
if (hash.ContainsKey(curr_sum))
maxLen = Math.Max(maxLen,
i - hash[curr_sum]);
// Store the index of the sum
else
// hash[curr_sum] = i;
hash.Add(curr_sum, i);
}
// Return the maximum
// length of required subString
return maxLen;
}
// Driver Code
public static void Main(String[] args)
{
String S = "geeksforgeeks";
int n = S.Length;
Console.Write(maxsubStringLength(
S.ToCharArray(), n));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to return the length of
// the longest subString having equal
// number of vowel and consonant
function maxsubStringLength(S, N)
{
let arr = Array.from({length: N}, (_, i) => 0);
// Generate the array
for(let i = 0; i < N; i++)
if (S[i] == 'a' || S[i] == 'e' ||
S[i] == 'i' || S[i] == 'o' ||
S[i] == 'u')
arr[i] = 1;
else
arr[i] = -1;
// Initialize variable
// to store result
let maxLen = 0;
// Stores the sum of subarray
let curr_sum = 0;
// Map to store indices of the sum
let hash = new Map();
// Loop through the array
for(let i = 0; i < N; i++)
{
curr_sum += arr[i];
// If sum is 0
if (curr_sum == 0)
// Count of vowels and consonants
// are equal
maxLen = Math.max(maxLen, i + 1);
// Update the maximum length
// of subString in HashMap
if (hash.has(curr_sum))
maxLen = Math.max(maxLen,
i - hash.get(curr_sum));
// Store the index of the sum
else
// hash[curr_sum] = i;
hash.set(curr_sum, i);
}
// Return the maximum
// length of required subString
return maxLen;
}
// Driver code
let S = "geeksforgeeks";
let n = S.length;
document.write(maxsubStringLength(S.split(''), n));
</script>
Producción:
10
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Stream_Cipher y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA