Given a string S of size N consisting of lowercase alphabets, the task is to print the length of the longest substring consisting only of vowels sorted in non-increasing order.
Examples:
Input: S = “ueiaoaeiouuoiea”
Output: 6
Explanation: The only substring which consists only of vowels in non-increasing order, is the substring {S[9], S[15]}, which is “uuoiea”.Input: S = “uuuioea”
Output: 0
Approach: The given problem can be solved using HashSet. Follow the steps below to solve the problem:
- Store all the vowels in an array, say ch[], in decreasing order.
- Initialize three variables res, j, and count as 0, to store the longest length of the required substring, to iterate over all vowels, and to store the length of the current substring satisfying the conditions respectively.
- Also, initialize a HashSet say mp to store all the distinct characters of the current substring satisfying the conditions.
- Iterate over the characters of the string S using a variable i and perform the following operations:
- If S[i] is equal to ch[j] then add S[i] to mp and then increment j and count by 1. If the size of mp is equal to 5, then update res to a maximum of res and count.
- Otherwise, if j + 1 is less than 5 and S[i] is equal to ch[j + 1], then increment j and count by 1 and add S[i] to mp. If the size of mp is equal to 5, then update res to a maximum of res and count.
- Otherwise, if S[i] is equal to ‘u‘ then assign 0 to j and 1 to count and add S[i] to mp. Otherwise, assign 0 to both j and count.
- After completing the above steps, print the value of res as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h>using namespace std;// Function to find length of the// longest substring consisting only// of vowels in non-increasing orderint count(string S, int N){ // Stores all vowels in decreasing order char ch[] = { 'u', 'o', 'i', 'e', 'a' }; // Stores current index of array ch[] int j = 0; // Stores the result int res = 0; // Stores the count // of current substring int count = 0; // Declare a HashSet to store the vowels unordered_set<char> mp; // Traverse the string, S for(int i = 0; i < N; ++i) { // If S[i] is equal to ch[j] if (S[i] == ch[j]) { // Increment count by 1 ++count; // Add S[i] in the mp mp.insert(S[i]); // If length of mp is 5, update res if (mp.size() == 5) { res = max(res, count); } } // Else if j+1 is less than 5 and // S[i] is equal to ch[j+1] else if (j + 1 < 5 && S[i] == ch[j + 1]) { // Add the S[i] in the mp mp.insert(S[i]); // Increment count by 1 ++count; // Increment j by 1 j++; // If length of mp is 5, update res if (mp.size() == 5) { res = max(res, count); } } else { // Clear the mp mp.clear(); // If S[i] is 'u' if (S[i] == 'u') { // Add S[i] in the mp mp.insert('u'); // Update j and assign 1 to count j = 0; count = 1; } // Else assign 0 to j and count else { j = 0; count = 0; } } } // Return the result return res;}// Driver Codeint main(){ string S = "ueiaoaeiouuoiea"; int N = S.size(); // Function Call cout << count(S, N); return 0;}// This code is contributed by Kingash |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to find length of the // longest substring consisting only // of vowels in non-increasing order static int count(String S, int N) { // Stores all vowels in decreasing order char ch[] = { 'u', 'o', 'i', 'e', 'a' }; // Stores current index of array ch[] int j = 0; // Stores the result int res = 0; // Stores the count // of current substring int count = 0; // Declare a HashSet to store the vowels HashSet<Character> mp = new HashSet<>(); // Traverse the string, S for (int i = 0; i < N; ++i) { // If S[i] is equal to ch[j] if (S.charAt(i) == ch[j]) { // Increment count by 1 ++count; // Add S[i] in the mp mp.add(S.charAt(i)); // If length of mp is 5, update res if (mp.size() == 5) { res = Math.max(res, count); } } // Else if j+1 is less than 5 and // S[i] is equal to ch[j+1] else if (j + 1 < 5 && S.charAt(i) == ch[j + 1]) { // Add the S[i] in the mp mp.add(S.charAt(i)); // Increment count by 1 ++count; // Increment j by 1 j++; // If length of mp is 5, update res if (mp.size() == 5) { res = Math.max(res, count); } } else { // Clear the mp mp.clear(); // If S[i] is 'u' if (S.charAt(i) == 'u') { // Add S[i] in the mp mp.add('u'); // Update j and assign 1 to count j = 0; count = 1; } // Else assign 0 to j and count else { j = 0; count = 0; } } } // Return the result return res; } // Driver Code public static void main(String[] args) { // Given Input String S = "ueiaoaeiouuoiea"; int N = S.length(); // Function Call System.out.println(count(S, N)); }} |
Python3
# Python3 program for the above approach # Function to find length of the# longest substring consisting only# of vowels in non-increasing orderdef count1(S, N): # Stores all vowels in decreasing order ch = ['u', 'o', 'i', 'e', 'a'] # Stores current index of array ch[] j = 0 # Stores the result res = 0 # Stores the count # of current substring count = 0; # Declare a HashSet to store the vowels mp = set() # Traverse the string, S for i in range(N): # If S[i] is equal to ch[j] if (S[i] == ch[j]): # Increment count by 1 count += 1 # Add S[i] in the mp mp.add(S[i]) # If length of mp is 5, update res if (len(mp) == 5): res = max(res, count) # Else if j+1 is less than 5 and # S[i] is equal to ch[j+1] elif (j + 1 < 5 and S[i] == ch[j + 1]): # Add the S[i] in the mp mp.add(S[i]) # Increment count by 1 count += 1 # Increment j by 1 j += 1 # If length of mp is 5, update res if (len(mp) == 5): res = max(res, count) else: # Clear the mp mp.clear() # If S[i] is 'u' if (S[i] == 'u'): # Add S[i] in the mp mp.add('u') # Update j and assign 1 to count j = 0 count = 1 # Else assign 0 to j and count else: j = 0 count = 0 # Return the result return res# Driver Codeif __name__ == '__main__': S = "ueiaoaeiouuoiea" N = len(S) # Function Call print(count1(S, N)) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to find length of the // longest substring consisting only // of vowels in non-increasing order static int count(string S, int N) { // Stores all vowels in decreasing order char[] ch = { 'u', 'o', 'i', 'e', 'a' }; // Stores current index of array ch[] int j = 0; // Stores the result int res = 0; // Stores the count // of current substring int count = 0; // Declare a HashSet to store the vowels HashSet<char> mp = new HashSet<char>(); // Traverse the string, S for (int i = 0; i < N; ++i) { // If S[i] is equal to ch[j] if (S[i] == ch[j]) { // Increment count by 1 ++count; // Add S[i] in the mp mp.Add(S[i]); // If length of mp is 5, update res if (mp.Count == 5) { res = Math.Max(res, count); } } // Else if j+1 is less than 5 and // S[i] is equal to ch[j+1] else if (j + 1 < 5 && S[i] == ch[j + 1]) { // Add the S[i] in the mp mp.Add(S[i]); // Increment count by 1 ++count; // Increment j by 1 j++; // If length of mp is 5, update res if (mp.Count == 5) { res = Math.Max(res, count); } } else { // Clear the mp mp.Clear(); // If S[i] is 'u' if (S[i] == 'u') { // Add S[i] in the mp mp.Add('u'); // Update j and assign 1 to count j = 0; count = 1; } // Else assign 0 to j and count else { j = 0; count = 0; } } } // Return the result return res; } // Driver Code public static void Main(string[] args) { // Given Input string S = "ueiaoaeiouuoiea"; int N = S.Length; // Function Call Console.WriteLine(count(S, N)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approach// Function to find length of the// longest substring consisting only// of vowels in non-increasing orderfunction count(S, N) { // Stores all vowels in decreasing order let ch = [ 'u', 'o', 'i', 'e', 'a' ]; // Stores current index of array ch[] let j = 0; // Stores the result let res = 0; // Stores the count // of current substring let count = 0; // Declare a HashSet to store the vowels let mp = new Map(); // Traverse the string, S for(let i = 0; i < N; ++i) { // If S[i] is equal to ch[j] if (S[i] == ch[j]) { // Increment count by 1 ++count; // Add S[i] in the mp mp.set(S[i], ""); // If length of mp is 5, update res if (mp.size == 5) { res = Math.max(res, count); } } // Else if j+1 is less than 5 and // S[i] is equal to ch[j+1] else if (j + 1 < 5 && S[i] == ch[j + 1]) { // Add the S[i] in the mp mp.set(S[i], ""); // Increment count by 1 ++count; // Increment j by 1 j++; // If length of mp is 5, update res if (mp.size == 5) { res = Math.max(res, count); } } else { // Clear the mp mp.clear(); // If S[i] is 'u' if (S[i] == 'u') { // Add S[i] in the mp mp.set('u', ""); // Update j and assign 1 to count j = 0; count = 1; } // Else assign 0 to j and count else { j = 0; count = 0; } } } // Return the result return res;}// Driver Codelet S = "ueiaoaeiouuoiea";let N = S.length;// Function Calldocument.write(count(S, N));// This code is contributed by _saurabh_jaiswal</script> |
Output:
6
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
