Longest Ordered Subsequence of Vowels | C ++ program to find the longest subsequence of vowels in the specified order ; Mapping values for vowels ; Function to check if given subsequence contains all the vowels or not ; not contain vowel ; Function to find the longest subsequence of vowels in the given string in specified order ; If we have reached the end of the string , return the subsequence if it is valid , else return an empty list ; If there is no vowel in the subsequence yet , add vowel at current index if it is ' a ' , else move on to the next character in the string ; If the last vowel in the subsequence until now is same as the vowel at current index , add it to the subsequence ; If the vowel at the current index comes right after the last vowel in the subsequence , we have two options : either to add the vowel in the subsequence , or move on to next character . We choose the one which gives the longest subsequence . ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < char > vowels = { ' a ' , ' e ' , ' i ' , ' o ' , ' u ' } ; map < char , int > mapping = { { ' a ' , 0 } , { ' e ' , 1 } , { ' i ' , 2 } , { ' o ' , 3 } , { ' u ' , 4 } } ; bool isValidSequence ( string subList ) { for ( char c : vowels ) { if ( subList . find ( c ) == std :: string :: npos ) return 0 ; } return 1 ; } string longestSubsequence ( string str , string subList , int index ) { int len = str . length ( ) ; if ( index >= len ) { if ( isValidSequence ( subList ) ) return subList ; else return " " ; } else if ( subList . size ( ) == 0 ) { if ( str [ index ] != ' a ' ) return longestSubsequence ( str , " " , index + 1 ) ; else return longestSubsequence ( str , subList + str [ index ] , index + 1 ) ; } else if ( mapping [ subList [ subList . size ( ) - 1 ] ] == mapping [ str [ index ] ] ) return longestSubsequence ( str , subList + str [ index ] , index + 1 ) ; else if ( mapping [ subList [ subList . size ( ) - 1 ] ] + 1 == mapping [ str [ index ] ] ) { string sub1 = longestSubsequence ( str , subList + str [ index ] , index + 1 ) ; string sub2 = longestSubsequence ( str , subList , index + 1 ) ; if ( sub1 . length ( ) > sub2 . length ( ) ) return sub1 ; else return sub2 ; } else return longestSubsequence ( str , subList , index + 1 ) ; } int main ( ) { string str = " aeiaaioooauuaeiou " ; string subsequence = longestSubsequence ( str , " " , 0 ) ; if ( subsequence . length ( ) == 0 ) cout << " No ▁ subsequence ▁ possible STRNEWLINE " ; else cout << subsequence << " STRNEWLINE " ; }