Given string str consisting of lowercase alphabets, the task is to find the length of the longest substring such that all of its characters are vowels and no two adjacent alphabets are the same.
Examples:
Input: str = “aeoibsddaeiouudb”
Output: 5
Explanation:
The longest substring of vowels in which no two adjacent letters are same is “aeiou”
Length of substring = 5Input: str = “neveropen”
Output: 1
Explanation:
The longest substring of vowels in which no two adjacent letters are same are “e” or “o”.
Length of substring = 1
Naive Approach:
Generate all possible substrings from the given string. For each substring, check if all of its characters are vowels and no two adjacent characters are the same then compare the length of all such substrings and print the maximum length.
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 a// character is vowel or notbool isVowel(char c){ return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');}// Function to check a// substring is valid or notbool 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 alphabetsint 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 codeint main(){ string Str = "aeoibsddaeiouudb"; cout << findMaxLen(Str) << endl; return 0;} |
Java
// Java implementation of// the above approachimport java.io.*;class GFG{// Function to check a// character is vowel or notstatic boolean isVowel(char c){ return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');}// Function to check a// subString is valid or notstatic 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 alphabetsstatic 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 codepublic 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 notdef 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 notdef 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 alphabetsdef 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 codeif __name__ == "__main__": Str = "aeoibsddaeiouudb" print (findMaxLen(Str))# This code is contributed by Chitranayal |
C#
// C# implementation of the above approachusing System;class GFG{// Function to check a// character is vowel or notstatic bool isVowel(char c){ return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');}// Function to check a// substring is valid or notstatic 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 alphabetsstatic 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 codepublic 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 notfunction isVowel(c){ return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');}// Function to check a// subString is valid or notfunction 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 alphabetsfunction 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 Codelet Str = "aeoibsddaeiouudb";document.write(findMaxLen(Str));// This code is contributed by sanjoy_62</script> |
Output:
5
Time Complexity: O(N3)
Auxiliary Space: O(N), where N is the length of the given string.
Efficient Approach:
A linear-time solution is possible for this problem. A substring will be considered as valid if all of its characters are vowel and no two adjacent ones are the same. The idea is to traverse the string and keep track of the longest valid substring.
The following are the detailed steps:
- Create a variable cur to store the length of current valid substring and another variable maxVal to keep track of maximum cur found so far, initially, both are set to 0.
- If the character at index 0 is a vowel, then it is a valid substring of length 1, so maxVal = 1
- Traverse str starting from index 1. If the current character is not a vowel, no valid substring present, cur = 0
- If the current character is a vowel and
- Is different from the previous character, then includes it in the current valid substring and increment cur by 1. Update maxVal.
- Is the same as the previous character, then a new valid substring starts from this character with cur reset to 1.
- The final value of maxVal gives the answer.
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 a// character is vowel or notbool 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 alphabetsint 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 codeint main(){ string Str = "aeoibsddaeiouudb"; cout << findMaxLen(Str) << endl; return 0;} |
Java
// Java implementation of// the above approachpublic 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 notdef 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 alphabetsdef 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 approachusing 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> |
Output:
5
Time complexity: O(N)
Auxiliary Space: 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!
