Given a non-empty string S, the task is to print the longest subsequence from the string S which contains alternating vowels and consonants.
Note: If multiple such subsequences exist having the same length, print the subsequence having the maximum sum of ASCII values of its characters.
Examples:
Input: S = “neveropen”
Output: gesores
Explanation: “gekorek”, “gekores”, “gekogek”, “gekoges”, “gesorek”, “gesores”, “gesogek”, “gesoges”, “geforek”, “gefores”, “gefogek” and “gefoges” are the possible longest subsequences with alternating consonants and vowels. “gesores” is the subsequence with maximum sum of ASCII values of characters and hence it is the solution.Input: S = “ababababab”
Output: ababababab
Explanation: “ababababab” is the longest possible subsequence containing alternating vowels and consonants.
Approach:
Follow the steps below to solve the problem:
- Store the ASCII value of the first character of S as the maximum of the current block (maxi) and type of the character in flag. If the character is consonant, set flag as 0 and 1 otherwise.
- Traverse through the rest of the string.
- For every character, check if it belongs to the same block as that of the previous character or not.
- If it belongs to same block, update maxi to max(maxi, ASCII value of ith character).
- Otherwise, append the character with ASCII value maxi to the answer. Store the ASCII value of current ith character as maxi. Update flag to (flag + 1)%2 to denote the type of the current character.
- After traversal of entire string, add the character with ASCII value maxi to the answer. Print the final string representing the subsequence.
Below code is the implementation of the above approach:
C++
// C++ program to find the longest// subsequence containing alternating// vowels and consonants#include <bits/stdc++.h>using namespace std;// Function that return 1 or 0// if the given character is// vowel or consonant respectivelyint isVowel(char c){ // Returns 1 if c is vowel if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return 1; // Returns 0 if // c is consonant return 0;}// Function to find the longest// subsequence containing// alternate vowels and// consonantsstring Subsequence(string str){ // Store the length // of the string int n = str.length(); // Assume first character // to be consonant int flag = 0; // If first character is vowel if (isVowel(str[0]) == 1) flag = 1; // Store the ASCII value int maxi = (int)str[0]; // Stores the final answer string ans = ""; for(int i = 1; i < n; i++) { // If the current character belongs // to same category (Vowel / Consonant) // as the previous character if (isVowel(str[i]) == flag) { // Store the maximum ASCII value maxi = max(maxi, (int)str[i]); } // Otherwise else { // Store the character with // maximum ASCII value from // the previous block ans += (char)(maxi); // Store the ASCII of the // current character as the // maximum of the current block maxi = (int)str[i]; // Switch the type of the // current block flag = (flag + 1) % 2; } } // Store the character with // maximum ASCII value // from the last block ans += (char)(maxi); // Return the result return ans;}// Driver codeint main(){ string str = "neveropen"; cout << (Subsequence(str));}// This code is contributed by chitranayal |
Java
// Java program to find the longest // subsequence containing alternating // vowels and consonants import java.util.*; import java.lang.*; import java.io.*; import java.math.*; class GFG { // Function that return 1 or 0 // if the given character is // vowel or consonant respectively static int isVowel(char c) { // Returns 1 if c is vowel if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return 1; // Returns 0 if // c is consonant return 0; } // Function to find the longest // subsequence containing // alternate vowels and // consonants static String Subsequence(String str) { // Store the length // of the string int n = str.length(); // Assume first character // to be consonant int flag = 0; // If first character is vowel if (isVowel(str.charAt(0)) == 1) flag = 1; // Store the ASCII value int maxi = (int)str.charAt(0); // Stores the final answer String ans = ""; for (int i = 1; i < n; i++) { // If the current character belongs // to same category (Vowel / Consonant) // as the previous character if (isVowel(str.charAt(i)) == flag) { // Store the maximum ASCII value maxi = Math.max(maxi, (int)str.charAt(i)); } // Otherwise else { // Store the character with // maximum ASCII value from // the previous block ans += (char)(maxi); // Store the ASCII of the // current character as the // maximum of the current block maxi = (int)str.charAt(i); // Switch the type of the // current block flag = (flag + 1) % 2; } } // Store the character with // maximum ASCII value // from the last block ans += (char)(maxi); // Return the result return ans; } // Driver Program public static void main(String[] args) { String str = "neveropen"; System.out.println(Subsequence(str)); } } |
Python3
# Python3 program to find the longest# subsequence containing alternating# vowels and consonantsdef isVowel(c): # boolean function that check whether # the given char is vowel or not # and returns a boolean value respectively vowels=['a','e','i','o','u'] if(c in vowels): return True return Falsedef Subsequence(str): #string that stores the final result ans='' flag=(isVowel(str[0])) #taking the first character #as the maximum ASCII valued char maxi=ord(str[0]) for i in range(1,len(str)): # If the current character belongs to # same category(Vowel / Consonant) as the # previous character if (isVowel(str[i]) == flag): # choosing a maximum ASCII valued char maxi=max(maxi,ord(str[i])) #otherwise else: ans=ans+chr(maxi) maxi=ord(str[i]) #toggling the flag flag=not(flag) #adding the last char to the answer ans=ans+chr(maxi) return ans #Driver program if __name__ == "__main__": input_string ='neveropen' print(Subsequence(input_string)) # Contributed by # Nvss Maneesh Gupta |
C#
// C# program to find the longest // subsequence containing alternating // vowels and consonants using System; class GFG{ // Function that return 1 or 0 // if the given character is // vowel or consonant respectively static int isVowel(char c) { // Returns 1 if c is vowel if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return 1; // Returns 0 if // c is consonant return 0; } // Function to find the longest // subsequence containing // alternate vowels and // consonants static String Subsequence(String str) { // Store the length // of the string int n = str.Length; // Assume first character // to be consonant int flag = 0; // If first character is vowel if (isVowel(str[0]) == 1) flag = 1; // Store the ASCII value int maxi = (int)str[0]; // Stores the readonly answer String ans = ""; for(int i = 1; i < n; i++) { // If the current character belongs // to same category (Vowel / Consonant) // as the previous character if (isVowel(str[i]) == flag) { // Store the maximum ASCII value maxi = Math.Max(maxi, (int)str[i]); } // Otherwise else { // Store the character with // maximum ASCII value from // the previous block ans += (char)(maxi); // Store the ASCII of the // current character as the // maximum of the current block maxi = (int)str[i]; // Switch the type of the // current block flag = (flag + 1) % 2; } } // Store the character with // maximum ASCII value // from the last block ans += (char)(maxi); // Return the result return ans; } // Driver code public static void Main(String[] args) { String str = "neveropen"; Console.WriteLine(Subsequence(str)); } } // This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to find the longest// subsequence containing alternating// vowels and consonants// Function that return 1 or 0// if the given character is// vowel or consonant respectivelyfunction isVowel(c){ // Returns 1 if c is vowel if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return 1; // Returns 0 if // c is consonant return 0;}// Function to find the longest// subsequence containing// alternate vowels and// consonantsfunction Subsequence(str){ // Store the length // of the string var n = str.length; // Assume first character // to be consonant var flag = 0; // If first character is vowel if (isVowel(str[0]) == 1) flag = 1; // Store the ASCII value var maxi = (str[0].charCodeAt(0)); // Stores the final answer var ans = ""; for(var i = 1; i < n; i++) { // If the current character belongs // to same category (Vowel / Consonant) // as the previous character if (isVowel(str[i]) == flag) { // Store the maximum ASCII value maxi = Math.max(maxi, str[i].charCodeAt(0)); } // Otherwise else { // Store the character with // maximum ASCII value from // the previous block ans += String.fromCharCode(maxi); // Store the ASCII of the // current character as the // maximum of the current block maxi = str[i].charCodeAt(0); // Switch the type of the // current block flag = (flag + 1) % 2; } } // Store the character with // maximum ASCII value // from the last block ans += String.fromCharCode(maxi); // Return the result return ans;}// Driver codevar str = "neveropen";document.write(Subsequence(str));// This code is contributed by rrrtnx.</script> |
Output
gesores
Time Complexity: O(N)
Auxiliary Space: O(N), where N is the length of the given string.
Method 2: Using Recursion
Approach:
- The given problem can be solved using recursion where we generate all possible subsequences of the given string and check if they contain alternating vowels and consonants.
- If a subsequence satisfies this condition, then we check if it is longer than the current longest subsequence and update the longest subsequence accordingly.
- The recursion continues until we have generated all possible subsequences of the given string.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;bool isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';}string longestSubsequence(string s, string current, string longest) { if (s.length() == 0) { bool isAlternate = true; int sum = 0; for (int i = 0; i < current.length() - 1; i++) { if (isVowel(current[i]) == isVowel(current[i + 1])) { isAlternate = false; break; } } if (isAlternate) { if (current.length() > longest.length() || (current.length() == longest.length() && accumulate(current.begin(), current.end(), 0) > accumulate(longest.begin(), longest.end(), 0))) { longest = current; } } return longest; } longest = longestSubsequence(s.substr(1), current + s[0], longest); longest = longestSubsequence(s.substr(1), current, longest); return longest;}int main() { string s= "neveropen" ; string longest = longestSubsequence(s, "", ""); cout << longest << endl; return 0;} |
Java
import java.util.*;public class GFG { // Function to check if a character is a vowel public static boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } // Function to find the longest alternating subsequence // of a string public static String longestSubsequence(String s, String current, String longest) { if (s.length() == 0) { // Check if the current subsequence is // alternating (consecutive vowels and // consonants) boolean isAlternate = true; for (int i = 0; i < current.length() - 1; i++) { if (isVowel(current.charAt(i)) == isVowel(current.charAt(i + 1))) { isAlternate = false; break; } } if (isAlternate) { // If the current subsequence is // alternating, compare its length and ASCII // sum with the longest subsequence if (current.length() > longest.length() || (current.length() == longest.length() && getASCIISum(current) > getASCIISum(longest))) { longest = current; } } return longest; } // Recursively find the longest alternating // subsequence by including or excluding the current // character longest = longestSubsequence( s.substring(1), current + s.charAt(0), longest); longest = longestSubsequence(s.substring(1), current, longest); return longest; } // Function to calculate the ASCII sum of a string public static int getASCIISum(String s) { int sum = 0; for (char c : s.toCharArray()) { sum += c; } return sum; } // Driver code public static void main(String[] args) { String s = "neveropen"; String longest = longestSubsequence(s, "", ""); System.out.println(longest); }} |
Python
def is_vowel(c): # Function to check if a character is a vowel return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'def longest_subsequence(s, current, longest): # Recursive function to find the longest subsequence with alternating vowels and consonants if len(s) == 0: # Base case: if the input string is empty is_alternate = True for i in range(len(current) - 1): if is_vowel(current[i]) == is_vowel(current[i + 1]): # If two consecutive characters have the same type (vowel or consonant) is_alternate = False break if is_alternate: # If the current subsequence has alternating vowels and consonants if len(current) > len(longest) or (len(current) == len(longest) and sum(ord(c) for c in current) > sum(ord(c) for c in longest)): # If the current subsequence is longer or has a greater ASCII sum than the longest found so far longest = current return longest # Recursively explore two possibilities: including the current character or excluding it longest = longest_subsequence(s[1:], current + s[0], longest) longest = longest_subsequence(s[1:], current, longest) return longestif __name__ == "__main__": s = "neveropen" longest = longest_subsequence(s, "", "") print(longest) |
C#
using System;class GFG { static bool IsVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } static string LongestSubsequence(string s, string current, string longest) { if (s.Length == 0) { bool isAlternate = true; for (int i = 0; i < current.Length - 1; i++) { if (IsVowel(current[i]) == IsVowel(current[i + 1])) { isAlternate = false; break; } } if (isAlternate) { if (current.Length > longest.Length || (current.Length == longest.Length && GetAsciiSum(current) > GetAsciiSum(longest))) { longest = current; } } return longest; } longest = LongestSubsequence( s.Substring(1), current + s[0], longest); longest = LongestSubsequence(s.Substring(1), current, longest); return longest; } static int GetAsciiSum(string s) { int sum = 0; foreach(char c in s) { sum += (int)c; } return sum; } static void Main() { string s = "neveropen"; string longest = LongestSubsequence(s, "", ""); Console.WriteLine(longest); }} |
Javascript
function isVowel(c) { return c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u';}function longestSubsequence(s, current, longest) { if (s.length === 0) { let isAlternate = true; for (let i = 0; i < current.length - 1; i++) { if (isVowel(current[i]) === isVowel(current[i + 1])) { isAlternate = false; break; } } if (isAlternate) { if (current.length > longest.length || (current.length === longest.length && [...current].reduce((acc, val) => acc + val.charCodeAt(0), 0) > [...longest].reduce((acc, val) => acc + val.charCodeAt(0), 0))) { longest = current; } } return longest; } longest = longestSubsequence(s.substr(1), current + s[0], longest); longest = longestSubsequence(s.substr(1), current, longest); return longest;}function main() { const s = "neveropen"; const longest = longestSubsequence(s, "", ""); console.log(longest);}main(); |
Output
gesores
Time Complexity: O(2^n), where n is the length of the given string.
Auxiliary Space: O(1), No extra space is being used.
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!
