Dada la string str que consta de alfabetos en minúsculas, la tarea es encontrar la longitud de la substring más larga de modo que todos sus caracteres sean vocales y no haya dos alfabetos adyacentes iguales.
Ejemplos:
Entrada: str = “aeoibsddaeiouudb”
Salida: 5
Explicación:
La substring de vocales más larga en la que no hay dos letras adyacentes iguales es “aeiou”
Longitud de la substring = 5Entrada: str = «geeksforgeeks»
Salida: 1
Explicación:
La substring de vocales más larga en la que no hay dos letras adyacentes iguales es «e» u «o».
Longitud de la substring = 1
Enfoque ingenuo:
genera todas las substrings posibles a partir de la string dada. Para cada substring, verifique si todos sus caracteres son vocales y no hay dos caracteres adyacentes iguales, luego compare la longitud de todas esas substrings e imprima la longitud máxima.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check a
// character is vowel or not
bool isVowel(char c)
{
return (c == 'a' || c == 'e'
|| c == 'i' || c == 'o'
|| c == 'u');
}
// Function to check a
// substring is valid or not
bool isValid(string& s)
{
int n = s.size();
// If size is 1 then
// check only first character
if (n == 1)
return (isVowel(s[0]));
// If 0'th character is
// not vowel then invalid
if (isVowel(s[0]) == false)
return false;
for (int i = 1; i < n; i++) {
// If two adjacent characters
// are same or i'th char is
// not vowel then invalid
if (s[i] == s[i - 1]
|| !isVowel(s[i]))
return false;
}
return true;
}
// Function to find length
// of longest substring
// consisting only of
// vowels and no similar
// adjacent alphabets
int findMaxLen(string& s)
{
// Stores max length
// of valid substring
int maxLen = 0;
int n = s.length();
for (int i = 0; i < n; i++) {
// For current substring
string temp = "";
for (int j = i; j < n; j++) {
temp = temp + s[j];
// Check if substring
// is valid
if (isValid(temp))
// Size of substring
// is (j-i+1)
maxLen = max(
maxLen, (j - i + 1));
}
}
return maxLen;
}
// Driver code
int main()
{
string Str = "aeoibsddaeiouudb";
cout << findMaxLen(Str) << endl;
return 0;
}
Java
// Java implementation of
// the above approach
import java.io.*;
class GFG{
// Function to check a
// character is vowel or not
static boolean isVowel(char c)
{
return (c == 'a' || c == 'e' ||
c == 'i' || c == 'o' ||
c == 'u');
}
// Function to check a
// subString is valid or not
static boolean isValid(String s)
{
int n = s.length();
// If size is 1 then
// check only first character
if (n == 1)
return (isVowel(s.charAt(0)));
// If 0'th character is
// not vowel then invalidlen
if (isVowel(s.charAt(0)) == false)
return false;
for (int i = 1; i < n; i++)
{
// If two adjacent characters
// are same or i'th char is
// not vowel then invalid
if (s.charAt(i) == s.charAt(i - 1) ||
!isVowel(s.charAt(i)))
return false;
}
return true;
}
// Function to find length
// of longest subString
// consisting only of
// vowels and no similar
// adjacent alphabets
static int findMaxLen(String s)
{
// Stores max length
// of valid subString
int maxLen = 0;
int n = s.length();
for (int i = 0; i < n; i++)
{
// For current subString
String temp = "";
for (int j = i; j < n; j++)
{
temp = temp + s.charAt(j);
// Check if subString
// is valid
if (isValid(temp))
// Size of subString
// is (j-i+1)
maxLen = Math.max(maxLen,
(j - i + 1));
}
}
return maxLen;
}
// Driver code
public static void main (String[] args)
{
String Str = "aeoibsddaeiouudb";
System.out.println(findMaxLen(Str));
}
}
// This code is contributed by shubhamcoder
Python3
# Python3 implementation of # the above approach # Function to check a # character is vowel or not def isVowel(c): return (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u') # Function to check a # substring is valid or not def isValid(s): n = len(s) # If size is 1 then # check only first character if (n == 1): return (isVowel(s[0])) # If 0'th character is # not vowel then invalid if (isVowel(s[0]) == False): return False for i in range (1, n): # If two adjacent characters # are same or i'th char is # not vowel then invalid if (s[i] == s[i - 1] or not isVowel(s[i])): return False return True # Function to find length # of longest substring # consisting only of # vowels and no similar # adjacent alphabets def findMaxLen(s): # Stores max length # of valid substring maxLen = 0 n = len(s) for i in range (n): # For current substring temp = "" for j in range (i, n): temp = temp + s[j] # Check if substring # is valid if (isValid(temp)): # Size of substring # is (j-i+1) maxLen = (max(maxLen, (j - i + 1))) return maxLen # Driver code if __name__ == "__main__": Str = "aeoibsddaeiouudb" print (findMaxLen(Str)) # This code is contributed by Chitranayal
C#
// C# implementation of the above approach
using System;
class GFG{
// Function to check a
// character is vowel or not
static bool isVowel(char c)
{
return (c == 'a' || c == 'e' ||
c == 'i' || c == 'o' ||
c == 'u');
}
// Function to check a
// substring is valid or not
static bool isValid(string s)
{
int n = s.Length;
// If size is 1 then
// check only first character
if (n == 1)
return (isVowel(s[0]));
// If 0'th character is
// not vowel then invalid
if (isVowel(s[0]) == false)
return false;
for(int i = 1; i < n; i++)
{
// If two adjacent characters
// are same or i'th char is
// not vowel then invalid
if (s[i] == s[i - 1] ||
!isVowel(s[i]))
return false;
}
return true;
}
// Function to find length
// of longest substring
// consisting only of
// vowels and no similar
// adjacent alphabets
static int findMaxLen(string s)
{
// Stores max length
// of valid substring
int maxLen = 0;
int n = s.Length;
for(int i = 0; i < n; i++)
{
// For current substring
string temp = "";
for(int j = i; j < n; j++)
{
temp = temp + s[j];
// Check if substring
// is valid
if (isValid(temp))
// Size of substring
// is (j-i+1)
maxLen = Math.Max(maxLen,
(j - i + 1));
}
}
return maxLen;
}
// Driver code
public static void Main()
{
string Str = "aeoibsddaeiouudb";
Console.WriteLine(findMaxLen(Str));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// JavaScript implementation of the
// above approach
// Function to check a
// character is vowel or not
function isVowel(c)
{
return (c == 'a' || c == 'e' ||
c == 'i' || c == 'o' ||
c == 'u');
}
// Function to check a
// subString is valid or not
function isValid(s)
{
let n = s.length;
// If size is 1 then
// check only first character
if (n == 1)
return (isVowel(s[0]));
// If 0'th character is
// not vowel then invalidlen
if (isVowel(s[0]) == false)
return false;
for(let i = 1; i < n; i++)
{
// If two adjacent characters
// are same or i'th char is
// not vowel then invalid
if (s[i] == s[i - 1] ||
!isVowel(s[i]))
return false;
}
return true;
}
// Function to find length
// of longest subString
// consisting only of
// vowels and no similar
// adjacent alphabets
function findMaxLen(s)
{
// Stores max length
// of valid subString
let maxLen = 0;
let n = s.length;
for(let i = 0; i < n; i++)
{
// For current subString
let temp = "";
for(let j = i; j < n; j++)
{
temp = temp + s[j];
// Check if subString
// is valid
if (isValid(temp))
// Size of subString
// is (j-i+1)
maxLen = Math.max(maxLen,
(j - i + 1));
}
}
return maxLen;
}
// Driver Code
let Str = "aeoibsddaeiouudb";
document.write(findMaxLen(Str));
// This code is contributed by sanjoy_62
</script>
Producción:
5
Complejidad temporal: O(N 3 )
Enfoque eficiente:
una solución de tiempo lineal es posible para este problema. Una substring se considerará válida si todos sus caracteres son vocales y no hay dos adyacentes iguales. La idea es atravesar la string y realizar un seguimiento de la substring válida más larga.
Los siguientes son los pasos detallados:
- Cree una variable cur para almacenar la longitud de la substring válida actual y otra variable maxVal para realizar un seguimiento de la cur máxima encontrada hasta el momento, inicialmente, ambas están configuradas en 0.
- Si el carácter en el índice 0 es una vocal, entonces es una substring válida de longitud 1, por lo que maxVal = 1
- Traverse str comenzando desde el índice 1. Si el carácter actual no es una vocal, no hay una substring válida presente, cur = 0
- Si el carácter actual es una vocal y
- Es diferente del carácter anterior, luego lo incluye en la substring válida actual e incrementa cur en 1. Actualice maxVal .
- Es lo mismo que el carácter anterior, luego una nueva substring válida comienza desde este carácter con el restablecimiento actual a 1.
- El valor final de maxVal da la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check a
// character is vowel or not
bool isvowel(char c)
{
return c == 'a' || c == 'e'
|| c == 'i' || c == 'o'
|| c == 'u';
}
// Function to find length
// of longest substring
// consisting only of
// vowels and no similar
// adjacent alphabets
int findMaxLen(string& s)
{
// Stores max length
// of valid subString
int maxLen = 0;
// Stores length of
// current valid subString
int cur = 0;
if (isvowel(s[0]))
cur = maxLen = 1;
for (int i = 1; i < s.length(); i++) {
if (isvowel(s[i])) {
// If curr and prev character
// are not same, include it
if (s[i] != s[i - 1])
cur += 1;
// If same as prev one, start
// new subString from here
else
cur = 1;
}
else {
cur = 0;
}
// Store max in maxLen
maxLen = max(cur, maxLen);
}
return maxLen;
}
// Driver code
int main()
{
string Str = "aeoibsddaeiouudb";
cout << findMaxLen(Str) << endl;
return 0;
}
Java
// Java implementation of
// the above approach
public class GFG {
// Function to check a
// character is vowel or not
static boolean isVowel(char x)
{
return (x == 'a' || x == 'e'
|| x == 'i' || x == 'o'
|| x == 'u');
}
// Function to find length
// of longest substring
// consisting only of
// vowels and no similar
// adjacent alphabets
static int findMaxLen(String s)
{
// Stores max length
// of valid subString
int maxLen = 0;
// Stores length of
// current valid subString
int cur;
if (isVowel(s.charAt(0)))
maxLen = 1;
cur = maxLen;
for (int i = 1; i < s.length(); i++) {
if (isVowel(s.charAt(i))) {
// If curr and prev character
// are not same, include it
if (s.charAt(i)
!= s.charAt(i - 1))
cur += 1;
// If same as prev one, start
// new subString from here
else
cur = 1;
}
else {
cur = 0;
}
// Store max in maxLen
maxLen = Math.max(cur, maxLen);
}
return maxLen;
}
// Driver code
public static void main(String[] args)
{
String Str = "aeoibsddaeiouudb";
System.out.println(findMaxLen(Str));
}
}
Python3
# Python implementation of # the above approach # Function to check a # character is vowel or not def isVowel(x): return (x == 'a' or x == 'e' or x == 'i' or x == 'o' or x == 'u'); # Function to find length # of longest substring # consisting only of # vowels and no similar # adjacent alphabets def findMaxLen(s): # Stores max length # of valid subString maxLen = 0 # Stores length of # current valid subString cur = 0 if(isVowel(s[0])): maxLen = 1; cur = maxLen for i in range(1, len(s)): if(isVowel(s[i])): # If curr and prev character # are not same, include it if(s[i] != s[i-1]): cur += 1 # If same as prev one, start # new subString from here else: cur = 1 else: cur = 0; # Store max in maxLen maxLen = max(cur, maxLen); return maxLen # Driver code Str = "aeoibsddaeiouudb" print(findMaxLen(Str))
C#
// C# implementation of
// the above approach
using System;
public class GFG {
// Function to check a
// character is vowel or not
public static bool isVowel(char x)
{
return (x == 'a' || x == 'e'
|| x == 'i' || x == 'o'
|| x == 'u');
}
// Function to find length
// of longest substring
// consisting only of
// vowels and no similar
// adjacent alphabets
public static int findMaxLen(string s)
{
// Stores max length
// of valid subString
int maxLen = 0;
// Stores length of
// current valid subString
int cur;
if (isVowel(s[0]))
maxLen = 1;
cur = maxLen;
for (int i = 1; i < s.Length; i++) {
if (isVowel(s[i])) {
// If curr and prev character
// are not same, include it
if (s[i] != s[i - 1])
cur += 1;
// If same as prev one, start
// new subString from here
else
cur = 1;
}
else {
cur = 0;
}
// Store max in maxLen
maxLen = Math.Max(cur, maxLen);
}
return maxLen;
}
// Driver code
public static void Main(string[] args)
{
string Str = "aeoibsddaeiouudb";
Console.WriteLine(findMaxLen(Str));
}
}
Javascript
<script>
// JavaScript implementation of
// the above approach
// Function to check a
// character is vowel or not
function isVowel(x) {
return x === "a" || x === "e" || x === "i" || x === "o" || x === "u";
}
// Function to find length
// of longest substring
// consisting only of
// vowels and no similar
// adjacent alphabets
function findMaxLen(s)
{
// Stores max length
// of valid subString
var maxLen = 0;
// Stores length of
// current valid subString
var cur;
if (isVowel(s[0])) maxLen = 1;
cur = maxLen;
for (var i = 1; i < s.length; i++) {
if (isVowel(s[i])) {
// If curr and prev character
// are not same, include it
if (s[i] !== s[i - 1]) cur += 1;
// If same as prev one, start
// new subString from here
else cur = 1;
} else {
cur = 0;
}
// Store max in maxLen
maxLen = Math.max(cur, maxLen);
}
return maxLen;
}
// Driver code
var Str = "aeoibsddaeiouudb";
document.write(findMaxLen(Str));
// This code is contributed by rdtank.
</script>
Producción:
5
Complejidad del tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por Chandan_Agrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA