Given string str of length N, the task is to find the longest substring which contains only vowels using the Binary Search technique.
Examples:
Input: str = “baeicba”
Output: 3
Explanation:
Longest substring which contains vowels only is “aei”.
Input: str = “aeiou”
Output: 5
Approach: Refer to the Longest substring of vowels for an approach in O(N) complexity.
Binary Search Approach: In this article, we are using a Binary Search based approach:
Follow the steps below to solve the problem:
- Apply binary search on the lengths ranging from 1 to N.
- For each mid-value check if there exists a substring of length mid consisting only of vowels in that substring.
- If there exists a substring of length mid, then update the value of max and update l as mid+1 to check if a substring of length greater than mid exists or not which consists only of vowels.
- If no such substring of length mid exists, update r as mid-1 to check if a substring of length smaller than mid exists or not which consists only of vowels.
- Repeat the above three steps until l is less than or equal to r.
- Return the max length obtained finally.
Below is the implementation of the above approach:
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std;// Function to check if a character// is vowel or notbool 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 vowelsbool 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 Searchint 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 Codeint main(){ string s = "sedrewaefhoiu"; cout << longestSubstring(s); return 0;} |
Java
// Java implementation of// the above approachimport java.util.*;class GFG{// Function to check if a character// is vowel or notstatic 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 vowelsstatic 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 Searchstatic 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 Codepublic static void main(String[] args){ String s = "sedrewaefhoiu"; System.out.print(longestSubString(s));}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 implementation of# the above approach# Function to check if a character# is vowel or notdef 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 vowelsdef 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 Searchdef 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 Codeif __name__ == "__main__": s = "sedrewaefhoiu" print (longestSubstring(s))# This code is contributed by Chitranayal |
C#
// C# implementation of// the above approachusing System;class GFG{ // Function to check if a character// is vowel or notstatic 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 vowelsstatic 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 Searchstatic 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 Codepublic static void Main(String[] args){ String s = "sedrewaefhoiu"; Console.Write(longestSubString(s));}}// This code is contributed by sapnasingh4991 |
Javascript
// JavaScript code to implement above approach.// Function to check if a character// is vowel or notfunction vowel(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 vowelsfunction check(s, k) { let cnt = new Array(26).fill(0); for (let i = 0; i < k - 1; i++) { cnt[s.charCodeAt(i) - 'a'.charCodeAt(0)] += 1; } // Applying sliding window to get // all substrings of length K for (let i = k - 1; i < s.length; i++) { cnt[s.charCodeAt(i) - 'a'.charCodeAt(0)] += 1; let flag1 = 0; for (let 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.charCodeAt(i - k + 1) - 'a'.charCodeAt(0)] -= 1; } return false;}// Function to perform Binary Searchfunction longestSubstring(s) { let l = 1; let r = s.length; let maxi = 0; // Doing binary search on the lengths while (l <= r) { let mid = Math.floor((l + r) / 2); if (check(s, mid)) { l = mid + 1; maxi = Math.max(maxi, mid); } else { r = mid - 1; } } return maxi;}// Driver Codelet s = "sedrewaefhoiu";console.log(longestSubstring(s));// contributed by adityasha4x71 |
Output:
3
Time Complexity: O(NlogN)
Auxiliary Space: O(26) => O(1), no extra space is required, so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
