Dada una string que consta solo de vocales, encuentre la subsecuencia más larga en la string dada de modo que conste de las cinco vocales y sea una secuencia de una o más a, seguidas de una o más e, seguidas de una o más i, seguidas de uno o más os y seguido por uno o más ues.
Si hay más de una subsecuencia más larga, imprima cualquiera.
Ejemplos:
Input : str = "aeiaaioooaauuaeiou" Output : {a, a, a, a, a, a, e, i, o, u} There are two possible outputs in this case: {a, a, a, a, a, a, e, i, o, u} and, {a, e, i, i, o, o, o, u, u, u} each of length 10 Input : str = "aaauuiieeou" Output : No subsequence possible
Enfoque:
recorremos todos los caracteres de la string de forma recursiva y seguimos las condiciones dadas:
- Si la subsecuencia está vacía, incluimos la vocal en el índice actual solo si es ‘a’. De lo contrario, pasamos al siguiente índice.
- Si la vocal en el índice actual es la misma que la última vocal incluida en la subsecuencia, la incluimos.
- Si la vocal en el índice actual es la siguiente vocal posible (es decir, a–> e–> i–> o–> u ) después de la última vocal incluida en la subsecuencia, tenemos dos opciones: incluirla o pasar a la siguiente. índice siguiente. Por lo tanto, elegimos el que da la subsecuencia más larga.
- Si no se cumple ninguna de las condiciones anteriores, pasamos al siguiente índice (para evitar un orden inválido de las vocales en la subsecuencia).
- Si hemos llegado al final de la string, comprobamos si la subsecuencia actual es válida o no. Si es válido (es decir, si contiene todas las vocales), lo devolvemos, de lo contrario, devolvemos una lista vacía.
Método 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the longest subsequence // of vowels in the specified order #include <bits/stdc++.h> using namespace std; vector<char> vowels = { 'a', 'e', 'i', 'o', 'u' }; // Mapping values for vowels map<char, int> mapping = { { 'a', 0 }, { 'e', 1 }, { 'i', 2 }, { 'o', 3 }, { 'u', 4 } }; // Function to check if given subsequence // contains all the vowels or not bool isValidSequence(string subList) { for(char c : vowels) { // not contain vowel if (subList.find(c) == std::string::npos) return 0; } return 1; } // Function to find the longest subsequence // of vowels in the given string in specified // order string longestSubsequence(string str, string subList, int index) { // If we have reached the end of the // string, return the subsequence // if it is valid, else return an // empty list int len = str.length(); if (index >= len) { if (isValidSequence(subList)) return subList; else return ""; } // 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 else if (subList.size() == 0) { if (str[index] != 'a') return longestSubsequence( str, "", index + 1); else return longestSubsequence( str, subList + str[index], index + 1); } // If the last vowel in the subsequence // until now is same as the vowel at // current index, add it to the subsequence else if (mapping[subList[subList.size() - 1]] == mapping[str[index]]) return longestSubsequence( str, subList+str[index], index + 1); // 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. 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); } // Driver Code int main() { string str= "aeiaaioooauuaeiou"; string subsequence = longestSubsequence( str, "", 0); if (subsequence.length() == 0) cout << "No subsequence possible\n"; else cout << subsequence << "\n"; } // This code is contributed by ajaykr00kj
Java
// Java program to find the longest subsequence // of vowels in the specified order import java.util.*; public class Main { static Vector<Character> vowels = new Vector<Character>(); // Mapping values for vowels static HashMap<Character, Integer> mapping = new HashMap<Character, Integer>(); // Function to check if given subsequence // contains all the vowels or not static boolean isValidSequence(String subList) { for(char c : vowels) { // not contain vowel if (subList.indexOf(c) < 0) return false; } return true; } // Function to find the longest subsequence // of vowels in the given string in specified // order static String longestSubsequence(String str, String subList, int index) { // If we have reached the end of the // string, return the subsequence // if it is valid, else return an // empty list int len = str.length(); if (index >= len) { if (isValidSequence(subList)) return subList; else return ""; } // 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 else if (subList.length() == 0) { if (str.charAt(index) != 'a') return longestSubsequence(str, "", index + 1); else return longestSubsequence(str, subList + str.charAt(index), index + 1); } // If the last vowel in the subsequence // until now is same as the vowel at // current index, add it to the subsequence else if (mapping.get(subList.charAt(subList.length() - 1)) == mapping.get(str.charAt(index))) return longestSubsequence(str, subList+str.charAt(index), index + 1); // 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. else if (mapping.get(subList.charAt(subList.length() - 1)) + 1 == mapping.get(str.charAt(index))) { String sub1 = longestSubsequence( str, subList + str.charAt(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); } public static void main(String[] args) { mapping.put('a', 0); mapping.put('e', 1); mapping.put('i', 2); mapping.put('o', 3); mapping.put('u', 4); vowels.add('a'); vowels.add('e'); vowels.add('i'); vowels.add('o'); vowels.add('u'); String str= "aeiaaioooauuaeiou"; String subsequence = longestSubsequence(str, "", 0); if (subsequence.length() == 0) System.out.println("No subsequence possible"); else { System.out.print("["); for(int i = 0; i < subsequence.length() - 1; i++) { System.out.print("'" + subsequence.charAt(i) + "'" + ", "); } System.out.print("'" + subsequence.charAt(subsequence.length()-1) + "'" + "]"); } } } // This code is contributed by mukesh07.
Python3
# Python3 program to find the longest subsequence # of vowels in the specified order vowels = ['a', 'e', 'i', 'o', 'u'] # Mapping values for vowels mapping = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4} # Function to check if given subsequence # contains all the vowels or not def isValidSequence(subList): for vowel in vowels: if vowel not in subList: return False return True # Function to find the longest subsequence of vowels # in the given string in specified order def longestSubsequence(string, subList, index): # If we have reached the end of the string, # return the subsequence # if it is valid, else return an empty list if index == len(string): if isValidSequence(subList) == True: return subList else: return [] else: # 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 len(subList) == 0: if string[index] != 'a': return longestSubsequence(string, subList, index + 1) else: return longestSubsequence(string, subList + \ [string[index]], index + 1) # If the last vowel in the subsequence until # now is same as the vowel at current index, # add it to the subsequence elif mapping[subList[-1]] == mapping[string[index]]: return longestSubsequence(string, subList + \ [string[index]], index + 1) # 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. elif (mapping[subList[-1]] + 1) == mapping[string[index]]: sub1 = longestSubsequence(string, subList + \ [string[index]], index + 1) sub2 = longestSubsequence(string, subList, index + 1) if len(sub1) > len(sub2): return sub1 else: return sub2 else: return longestSubsequence(string, subList, index + 1) # Driver Code if __name__ == "__main__": string = "aeiaaioooauuaeiou" subsequence = longestSubsequence(string, [], 0) if len(subsequence) == 0: print("No subsequence possible") else: print(subsequence)
C#
// C# program to find the longest subsequence // of vowels in the specified order using System; using System.Collections.Generic; class GFG { static List<char> vowels = new List<char>(new char[]{'a', 'e', 'i', 'o', 'u'}); // Mapping values for vowels static Dictionary<char, int> mapping = new Dictionary<char, int>(); // Function to check if given subsequence // contains all the vowels or not static bool isValidSequence(string subList) { foreach(char c in vowels) { // not contain vowel if (subList.IndexOf(c) < 0) return false; } return true; } // Function to find the longest subsequence // of vowels in the given string in specified // order static string longestSubsequence(string str, string subList, int index) { // If we have reached the end of the // string, return the subsequence // if it is valid, else return an // empty list int len = str.Length; if (index >= len) { if (isValidSequence(subList)) return subList; else return ""; } // 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 else if (subList.Length == 0) { if (str[index] != 'a') return longestSubsequence( str, "", index + 1); else return longestSubsequence( str, subList + str[index], index + 1); } // If the last vowel in the subsequence // until now is same as the vowel at // current index, add it to the subsequence else if (mapping[subList[subList.Length - 1]] == mapping[str[index]]) return longestSubsequence( str, subList+str[index], index + 1); // 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. else if (mapping[subList[subList.Length - 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); } static void Main() { mapping['a'] = 0; mapping['e'] = 1; mapping['i'] = 2; mapping['o'] = 3; mapping['u'] = 4; string str= "aeiaaioooauuaeiou"; string subsequence = longestSubsequence(str, "", 0); if (subsequence.Length == 0) Console.Write("No subsequence possible"); else { Console.Write("["); for(int i = 0; i < subsequence.Length - 1; i++) { Console.Write("'" + subsequence[i] + "'" + ", "); } Console.Write("'" + subsequence[subsequence.Length-1] + "'" + "]"); } } } // This code is contributed by divyeshrabadiya07.
Javascript
<script> // Javascript program to find the longest subsequence // of vowels in the specified order let vowels = [ 'a', 'e', 'i', 'o', 'u' ]; // Mapping values for vowels let mapping = new Map(); mapping['a'] = 0; mapping['e'] = 1; mapping['i'] = 2; mapping['o'] = 3; mapping['u'] = 4; // Function to check if given subsequence // contains all the vowels or not function isValidSequence(subList) { for(let c = 0; c < vowels.length; c++) { // not contain vowel if (!subList.includes(vowels)) return false; } return true; } // Function to find the longest subsequence // of vowels in the given string in specified // order function longestSubsequence(str, subList, index) { // If we have reached the end of the // string, return the subsequence // if it is valid, else return an // empty list let len = str.length; if (index >= len) { if (isValidSequence(subList)) return subList; else return ""; } // 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 else if (subList.length == 0) { if (str[index] != 'a') return longestSubsequence(str, "", index + 1); else return longestSubsequence(str, subList + str[index], index + 1); } // If the last vowel in the subsequence // until now is same as the vowel at // current index, add it to the subsequence else if (mapping[subList[subList.length - 1]] == mapping[str[index]]) return longestSubsequence(str, subList+str[index], index + 1); // 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. else if (mapping[subList[subList.length - 1]] + 1 == mapping[str[index]]) { let sub1 = longestSubsequence( str, subList + str[index], index + 1); let sub2 = longestSubsequence( str, subList, index + 1); if (sub1.length > sub2.length) return sub1; else return sub2; } else return longestSubsequence(str, subList, index + 1); } let str= "aeiaaioooauuaeiou"; let subsequence = longestSubsequence(str, "", 0); if (subsequence.length == 0) document.write("No subsequence possible"); else { document.write("[") for(let i = 0; i < subsequence.length - 1; i++) { document.write("'" + subsequence[i] + "'" + ", "); } document.write("'" + subsequence[subsequence.length-1] + "'" + "]"); } // This code is contributed by decode2207. </script>
aeiiooouuu
Método 2 (Programación Dinámica)
Python3
from random import choice def longest_subsequence(string): def helper(chosen="", i=0): if i == len(string): return chosen if set("aeiou").issubset(set(chosen)) else "" hashable = (chosen[-1] if chosen else None, len(chosen), i) if hashable in memo: return memo[hashable] if not chosen: res = helper("a" if string[i] == "a" else chosen, i + 1) elif chosen[-1] == string[i]: res = helper(chosen + string[i], i + 1) elif mapping[chosen[-1]] + 1 == mapping[string[i]]: sub1 = helper(chosen + string[i], i + 1) sub2 = helper(chosen, i + 1) res = sub1 if len(sub1) > len(sub2) else sub2 else: res = helper(chosen, i + 1) memo[hashable] = res return res mapping = {x: i for i, x in enumerate("aeiou")} memo = {} return helper() if __name__ == "__main__": tests = [ "aeiaaioooaauuaeiou", "aaauuiieeou", "".join(choice("aeiou") for _ in range(40)), "".join(choice("aeiou") for _ in range(900)) ] for string in tests: print("original:", string) subsequence = longest_subsequence(string) if subsequence: print("\nmax subsequence:", "".join(subsequence)) else: print("No subsequence possible") print("-" * 40, "\n")
original: aeiaaioooaauuaeiou max subsequence: aaaaaaeiou ---------------------------------------- original: aaauuiieeou No subsequence possible ---------------------------------------- original: uioeaieauaiuoaaauueaaouaaeeioeuauuieaiio max subsequence: aaaaaaaaaaeeiouuu ---------------------------------------- original: aaauauiieuaeaeeaaouaiauaiouoeaeaeiuuaiooaioeueiuuieaoaueuoeooeeoiiouaueaiauauooeuauuuuooaooieiuaeooueuuuooiiaaaeiaioeioiiuueieieaiaeuoiioaoieuooaaooaiuioeauieeeaeauiauoeueiaeeeooiaeoauioiuoaoaauuuueeaeuaaeiuaeiioaeaoiuaieaoioioiuoeeuouoiuaiuuaeioeoueaaoieaauoaeuaeiioieuoaiiiaeieiaueaaoeiiuuaoaiieoaioaeuouaeaouioeaauoiaiioeuiooeeeoiaeouuauuieeoooauueeuioiuaieuauaaeaeoaiooeaaoaiuouiuauauoaueeeuaeaioiooooaeeeoaaeaaeoaaiuaooooauiaiauaeuiueuiuoiieoeouiaueioioeeueieeaaieieuaaiuoeuiuouaeuiaiauoauuieuooaiouoeeaaoiaouoaaeiaiaiuuaeiiiaeuaiiouaiuuoiooiieoiiaiuoaueeiueoeeuauieoaauaeeiieioiiooaiiuaaeeoaoioauiouueoieaaaeueuuioeeauauaeuooooaiaeieaiieaaiaeeoeuiuaaeaiueaeiioaaeiooaouiaueeaoueueeeieuueaeoueaeaoiooiuioaoeaeaiuuoaeauoeeieeiuaiaaeauaauaiiuaauiiooioiuuauauuaouooeoeouioeoeoioaioieeuuuauuoouiaeueoiioaoeaoeaieeuouoeeouuoeioieuiaeioieieeeouiiueieeioeeuuaioeeoaaiaiooieeioiiouuaaoueueuaoaiaaeeeoouo max subsequence: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaeeeeeeeeeeeeeeeeeeiiiiiiooooooooooooooooooooooooooooooooouuuuuu ----------------------------------------
Complejidad temporal: O(m*n).
Espacio Auxiliar: O(m*n).
Enfoque alternativo (programación dinámica)
1. Este enfoque es similar a encontrar el concepto de subsecuencia creciente más larga.
2. Mantenemos dos arreglos
(i) dp que almacena la Subsecuencia Ordenada más larga que termina en el índice i
(ii) padre que almacena el índice del carácter anterior del carácter actual en la secuencia de vocales {a->e->i->o->u}
3. Para cada índice i, encontramos el valor máximo de dp[j] (0 <= j <i) donde s[j] es el carácter anterior de s[i] (carácter anterior en la secuencia de vocales) y parent[i] será ser j.
Implementación del enfoque anterior:
C++
#include <bits/stdc++.h> using namespace std; char getPrevChar(char c) { // previous characters in the order {a -> e -> i -> o -> // u} // previous of 'a' is 'a' (since 'a' can be placed // after 'a') if (c == 'a') return 'a'; if (c == 'e') return 'a'; if (c == 'i') return 'e'; if (c == 'o') return 'i'; else return 'o'; } int main() { string s = "aeiaaioooaauuaeiou"; int n = s.length(); vector<int> parent(n); // parent[i] ---> stores the previous character's index // to which it can be added for (int i = 0; i < n; i++) { parent[i] = i; // initial parent is itself } vector<int> dp(n, 0); // dp[i] ----> length of longest sequence ending at // index i; int ind = -1; for (int i = 0; i < n; i++) { if (s[i] == 'a') { dp[i] = 1; ind = i; break; } } // if there is no 'a' if (ind == -1) { cout << "NO POSSIBLE SEQUENCE" << endl; } // iterating from next character (after 'a') for (int i = ind + 1; i < n; i++) { int prev = getPrevChar(s[i]); // previous character of the current character in // vowel sequence {a -> e -> i -> o -> u} int cur = dp[i]; int par = i; for (int j = 0; j < i; j++) { if (s[j] == prev || s[j] == s[i]) { // if it matches its prev char or itself // then we can add to it if its length is // maximum than previous if (cur <= dp[j] + 1) { cur = dp[j] + 1; par = j; } } } dp[i] = max(cur, 1); parent[i] = par; } int lastIndex = -1; // finding the last occurrence of 'u' which will be last // occurrence of the sequence for (int i = n - 1; i >= 0; i--) { if (s[i] == 'u') { lastIndex = i; break; } } // if we do not find 'u' if (lastIndex == -1) { cout << "NO POSSIBLE SEQUENCE" << endl; exit(0); } string res = ""; while (lastIndex != parent[lastIndex]) { res += s[lastIndex]; lastIndex = parent[lastIndex]; } res += s[lastIndex]; // adding first character in the subsequence (which has // the parent as its index) if (s[lastIndex] != 'a') { cout << "NO POSSIBLE SEQUENCE" << endl; exit(0); } // reversing the string because we added from the last reverse(res.begin(), res.end()); cout << res << endl; return 0; }
aaaaaaeiou
Complejidad temporal: O(m*n).
Espacio Auxiliar: O(m*n).
Publicación traducida automáticamente
Artículo escrito por rituraj_jain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA