La substring más larga que consiste en vocales usando la búsqueda binaria

Dada la string str de longitud N , la tarea es encontrar la substring más larga que contiene solo vocales utilizando la técnica de búsqueda binaria .
Ejemplos:  

Entrada: str = “baeicba” 
Salida: 3 
Explicación: 
La substring más larga que contiene solo vocales es “aei”.
Entrada: str = “aeiou” 
Salida: 5 
 

Enfoque: consulte la substring de vocales más larga para un enfoque en complejidad O (N). 
Enfoque de búsqueda binaria: en este artículo, estamos utilizando un enfoque basado en  la búsqueda binaria
: siga los pasos a continuación para resolver el problema:  

1. Aplicar la búsqueda binaria en las longitudes que van desde 1 a N .
2. Para cada valor medio , compruebe si existe una substring de longitud media que consta solo de vocales en esa substring.
3. Si existe una substring de longitud mid , actualice el valor de max y actualice l como mid+1 para verificar si existe o no una substring de longitud mayor que mid que consiste solo en vocales.
4. Si no existe tal substring de longitud mid , actualice r como mid-1 para verificar si existe o no una substring de longitud menor que mid que consiste solo en vocales.
5. Repita los tres pasos anteriores hasta que l sea menor o igual que r.
6. Devuelve la longitud máxima obtenida finalmente.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a character
// is vowel or not
bool vowel(int vo)
{
    // 0-a 1-b 2-c and so on 25-z
    if (vo == 0 || vo == 4
        || vo == 8 || vo == 14
        || vo == 20)
        return true;
    else
        return false;
}
 
// Function to check if any
// substring of length k exists
// which contains only vowels
bool check(string s, int k)
{
    vector<int> cnt(26, 0);
    for (int i = 0; i < k - 1; i++) {
        cnt[s[i] - 'a']++;
    }
 
    // Applying sliding window to get
    // all substrings of length K
    for (int i = k - 1; i < s.size();
         i++) {
        cnt[s[i] - 'a']++;
        int flag1 = 0;
        for (int j = 0; j < 26; j++) {
            if (vowel(j) == false
                && cnt[j] > 0) {
                flag1 = 1;
                break;
            }
        }
        if (flag1 == 0)
            return true;
 
        // Remove the occurrence of
        // (i-k+1)th character
        cnt[s[i - k + 1] - 'a']--;
    }
 
    return false;
}
 
// Function to perform  Binary Search
int longestSubstring(string s)
{
    int l = 1, r = s.size();
    int maxi = 0;
 
    // Doing binary search on the lengths
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(s, mid)) {
            l = mid + 1;
            maxi = max(maxi, mid);
        }
        else
            r = mid - 1;
    }
    return maxi;
}
 
// Driver Code
int main()
{
    string s = "sedrewaefhoiu";
    cout << longestSubstring(s);
 
    return 0;
}

// Java implementation of
// the above approach
import java.util.*;
class GFG{
 
// Function to check if a character
// is vowel or not
static boolean vowel(int vo)
{
    // 0-a 1-b 2-c and so on 25-z
    if (vo == 0 || vo == 4 ||
        vo == 8 || vo == 14 ||
        vo == 20)
        return true;
    else
        return false;
}
 
// Function to check if any
// subString of length k exists
// which contains only vowels
static boolean check(String s, int k)
{
    int []cnt = new int[26];
    for (int i = 0; i < k - 1; i++)
    {
        cnt[s.charAt(i) - 'a']++;
    }
 
    // Applying sliding window to get
    // all subStrings of length K
    for (int i = k - 1; i < s.length(); i++)
    {
        cnt[s.charAt(i) - 'a']++;
        int flag1 = 0;
        for (int j = 0; j < 26; j++)
        {
            if (vowel(j) == false && cnt[j] > 0)
            {
                flag1 = 1;
                break;
            }
        }
        if (flag1 == 0)
            return true;
 
        // Remove the occurrence of
        // (i-k+1)th character
        cnt[s.charAt(i - k + 1) - 'a']--;
    }
 
    return false;
}
 
// Function to perform Binary Search
static int longestSubString(String s)
{
    int l = 1, r = s.length();
    int maxi = 0;
 
    // Doing binary search on the lengths
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(s, mid))
        {
            l = mid + 1;
            maxi = Math.max(maxi, mid);
        }
        else
            r = mid - 1;
    }
    return maxi;
}
 
// Driver Code
public static void main(String[] args)
{
    String s = "sedrewaefhoiu";
    System.out.print(longestSubString(s));
}
}
 
// This code is contributed by sapnasingh4991

# Python3 implementation of
# the above approach
 
# Function to check if a character
# is vowel or not
def vowel(vo):
 
    # 0-a 1-b 2-c and so on 25-z
    if (vo == 0 or vo == 4 or
        vo == 8 or vo == 14 or
        vo == 20):
        return True
    else:
        return False
 
# Function to check if any
# substring of length k exists
# which contains only vowels
def check(s, k):
 
    cnt = [0] * 26
    for i in range (k - 1):
        cnt[ord(s[i]) - ord('a')] += 1
    
    # Applying sliding window to get
    # all substrings of length K
    for i in range (k - 1, len(s)):
        cnt[ord(s[i]) - ord('a')] += 1
        flag1 = 0
        for j in range (26):
            if (vowel(j) == False
                and cnt[j] > 0):
                flag1 = 1
                break
         
        if (flag1 == 0):
            return True
 
        # Remove the occurrence of
        # (i-k+1)th character
        cnt[ord(s[i - k + 1]) - ord('a')] -= 1
 
    return False
 
# Function to perform  Binary Search
def longestSubstring(s):
 
    l = 1
    r = len(s)
    maxi = 0
 
    # Doing binary search on the lengths
    while (l <= r):
        mid = (l + r) // 2
        if (check(s, mid)):
            l = mid + 1
            maxi = max(maxi, mid)
        else:
            r = mid - 1
    return maxi
 
# Driver Code
if __name__ == "__main__": 
    s = "sedrewaefhoiu"
    print (longestSubstring(s))
 
# This code is contributed by Chitranayal

// C# implementation of
// the above approach
using System;
class GFG{
  
// Function to check if a character
// is vowel or not
static bool vowel(int vo)
{
    // 0-a 1-b 2-c and so on 25-z
    if (vo == 0 || vo == 4 ||
        vo == 8 || vo == 14 ||
        vo == 20)
        return true;
    else
        return false;
}
  
// Function to check if any
// subString of length k exists
// which contains only vowels
static bool check(String s, int k)
{
    int []cnt = new int[26];
    for (int i = 0; i < k - 1; i++)
    {
        cnt[s[i] - 'a']++;
    }
  
    // Applying sliding window to get
    // all subStrings of length K
    for (int i = k - 1; i < s.Length; i++)
    {
        cnt[s[i] - 'a']++;
        int flag1 = 0;
        for (int j = 0; j < 26; j++)
        {
            if (vowel(j) == false && cnt[j] > 0)
            {
                flag1 = 1;
                break;
            }
        }
        if (flag1 == 0)
            return true;
  
        // Remove the occurrence of
        // (i-k+1)th character
        cnt[s[i - k + 1] - 'a']--;
    }
  
    return false;
}
  
// Function to perform Binary Search
static int longestSubString(String s)
{
    int l = 1, r = s.Length;
    int maxi = 0;
  
    // Doing binary search on the lengths
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(s, mid))
        {
            l = mid + 1;
            maxi = Math.Max(maxi, mid);
        }
        else
            r = mid - 1;
    }
    return maxi;
}
  
// Driver Code
public static void Main(String[] args)
{
    String s = "sedrewaefhoiu";
    Console.Write(longestSubString(s));
}
}
 
// This code is contributed by sapnasingh4991

3

Complejidad temporal: O(NlogN) 
Espacio auxiliar: O(N)