BRUTE METHOD USING BIT MANIPULATION
Intuition:
- Declare a TreeSet<String> to store all the subsequences of string s.
- we pass the string s to a function where the subsequences are calculated.
- Then we check if first, the character of the string is a vowel and the last character is consonant or not.
- If so, then we add it to the ans list.
- At last, return the list.
Implementation:
C++
// C++ Program to generate all the subsequence // starting with vowel and ending with consonant. #include <bits/stdc++.h> using namespace std; set<string> st; // Function to find all the subsequences of a string void findSubsequences(string s) { int n = s.length(); for ( int num = 0; num < (1 << n); num++) { string sub = "" ; for ( int i = 0; i < n; i++) { if ((num & (1 << i)) != 0) { sub += s[i]; } } if (sub.length() > 0) { st.insert(sub); } } } // Check if char c is vowel or not bool isVowel( char c) { return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ); } // Check if char c is consonant or not bool isConsonant( char c) { return !(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ); } // Function to find all the subsequences starting with vowel and ending with consonant set<string> allPossibleSubsequences(string s) { findSubsequences(s); set<string> ans; for (string i : st) { if (isVowel(i[0]) && isConsonant(i[i.length() - 1])) { ans.insert(i); } } st.clear(); return ans; } // Driver code int main() { string s = "xabcef" ; set<string> result = allPossibleSubsequences(s); for (string str : result) { cout << str << " " ; } return 0; } // This code is contributed by Sundaram |
Java
// Java Program to generate all the subsequence // starting with vowel and ending with consonant. import java.io.*; import java.util.*; class GFG { static TreeSet<String> st = new TreeSet<String>(); // Function to find the subsequence static void findsubsequences(String s) { int n = s.length(); for ( int num = 0 ; num < ( 1 << n); num++) { String sub = "" ; for ( int i = 0 ; i < n; i++) { if ((num & ( 1 << i)) != 0 ) { sub += s.charAt(i); } } if (sub.length() > 0 ) { st.add(sub); } } } // Check if char c is vowel or not static boolean isVowel( char c) { return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ); } // Check if char c is consonant or not static boolean isConsonant( char c) { return !(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ); } static TreeSet<String> allPossibleSubsequences(String s) { findsubsequences(s); TreeSet<String> ans = new TreeSet<String>(); for (String i : st) { if (isVowel(i.charAt( 0 )) && isConsonant(i.charAt(i.length() - 1 ))) ans.add(i); } st.clear(); return ans; } // Driver Code public static void main(String[] args) { String s = "xabcef" ; System.out.println(allPossibleSubsequences(s)); } } |
Python3
def find_subsequences(s): subsequences = set () n = len (s) for num in range ( 1 << n): sub = "" for i in range (n): if (num & ( 1 << i)) ! = 0 : sub + = s[i] if sub: subsequences.add(sub) return subsequences def is_vowel(c): return c in [ 'a' , 'e' , 'i' , 'o' , 'u' ] def is_consonant(c): return not is_vowel(c) def all_possible_subsequences(s): subsequences = find_subsequences(s) result = set () for i in subsequences: if is_vowel(i[ 0 ]) and is_consonant(i[ - 1 ]): result.add(i) return result # Driver code if __name__ = = "__main__" : input_string = "xabcef" result = all_possible_subsequences(input_string) for res in result: print (res, end = " " ) |
C#
// C# Program to generate all the subsequence // starting with vowel and ending with consonant. using System; using System.Collections.Generic; class GFG { static SortedSet< string > st = new SortedSet< string >(); // Function to find the subsequence static void findsubsequences( string s) { int n = s.Length; for ( int num = 0; num < (1 << n); num++) { string sub = "" ; for ( int i = 0; i < n; i++) { if ((num & (1 << i)) != 0) { sub += s[i]; } } if (sub.Length > 0) { st.Add(sub); } } } // Check if char c is vowel or not static bool isVowel( char c) { return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ); } // Check if char c is consonant or not static bool isConsonant( char c) { return !(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ); } static SortedSet< string > allPossibleSubsequences( string s) { findsubsequences(s); SortedSet< string > ans = new SortedSet< string >(); foreach ( string i in st) { if (isVowel(i[0]) && isConsonant(i[i.Length - 1])) ans.Add(i); } st.Clear(); return ans; } // Driver Code public static void Main( string [] args) { string s = "xabcef" ; SortedSet< string > result = allPossibleSubsequences(s); foreach ( string str in result) { Console.Write(str+ " " ); } } } // This code is contributed by Utkarsh Kumar |
Javascript
let st = new Set(); // Function to find all the subsequences of a string function findSubsequences(s) { let n = s.length; for (let num = 0; num < (1 << n); num++) { let sub = "" ; for (let i = 0; i < n; i++) { if ((num & (1 << i)) !== 0) { sub += s[i]; } } if (sub.length > 0) { st.add(sub); } } } // Check if char c is vowel or not function isVowel(c) { return (c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u' ); } // Check if char c is consonant or not function isConsonant(c) { return !(c === 'a' || c === 'e' || c === 'i' || c === 'o' || c === 'u' ); } // Function to find all the subsequences starting with vowel // and ending with consonant function allPossibleSubsequences(s) { findSubsequences(s); let ans = new Set(); for (let i of st) { if (isVowel(i[0]) && isConsonant(i[i.length - 1])) { ans.add(i); } } st.clear(); return ans; } // Driver code let inputString = "xabcef" ; let result = allPossibleSubsequences(inputString); console.log([...result].join( " " )); |
[ab, abc, abcef, abcf, abef, abf, ac, acef, acf, aef, af, ef]
Time Complexity: O(n* logn* (2^n))
Space Complexity: O(N) since we are using Tree Set.
Explanation of the Algorithm:
- Step 1: Iterate over the entire String
- Step 2: check if the ith character for vowel
- Step 3: If true iterate the string from the end,
if false move to next iteration- Step 4: check the jth character for consonant
if false move to next iteration
if true perform the following- Step 5: Add the substring starting at index i and ending at index j to the hashset.
- Step 6: Iterate over the substring drop each character and recur to generate all its subString
C++
// C++ program to generate all the subse-quence // starting with vowel and ending with consonant. #include <bits/stdc++.h> using namespace std; // Set to store all the subsequences set<string> st; // Utility method to check vowel bool isVowel( char c) { return (c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u' ); } // Utility method to check consonant bool isConsonant( char c) { return !isVowel(c); } // It computes all the possible substring that // starts with vowel and end with consonant void subsequence(string str) { // iterate over the entire string for ( int i = 0; i < str.length(); i++) { // test ith character for vowel if (isVowel(str[i])) { // if the ith character is vowel // iterate from end of the string // and check for consonant. for ( int j = str.length() - 1; j >= i; j--) { // test jth character for consonant. if (isConsonant(str[j])) { // once we get a consonant add it to // the hashset string str_sub = str.substr(i, j + 1); st.insert(str_sub); // drop each character of the substring // and recur to generate all subsequence // of the substring for ( int k = 1; k < str_sub.length() - 1; k++) { string sb = str_sub; sb.erase(sb.begin() + k); subsequence(sb); } } } } } } // Driver Code int main() { string s = "xabcef" ; subsequence(s); for ( auto i : st) cout << i << " " ; cout << endl; return 0; } // This code is contributed by // sanjeev2552 |
Java
// Java Program to generate all the subsequence // starting with vowel and ending with consonant. import java.util.HashSet; public class Subsequence { // Set to store all the subsequences static HashSet<String> st = new HashSet<>(); // It computes all the possible substring that // starts with vowel and end with consonant static void subsequence(String str) { // iterate over the entire string for ( int i = 0 ; i < str.length(); i++) { // test ith character for vowel if (isVowel(str.charAt(i))) { // if the ith character is vowel // iterate from end of the string // and check for consonant. for ( int j = (str.length() - 1 ); j >= i; j--) { // test jth character for consonant. if (isConsonant(str.charAt((j)))) { // once we get a consonant add it to // the hashset String str_sub = str.substring(i, j + 1 ); st.add(str_sub); // drop each character of the substring // and recur to generate all subsequence // of the substring for ( int k = 1 ; k < str_sub.length() - 1 ; k++) { StringBuffer sb = new StringBuffer(str_sub); sb.deleteCharAt(k); subsequence(sb.toString()); } } } } } } // Utility method to check vowel static boolean isVowel( char c) { return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ); } // Utility method to check consonant static boolean isConsonant( char c) { return !isVowel(c); } // Driver code public static void main(String[] args) { String s = "xabcef" ; subsequence(s); System.out.println(st); } } |
Python3
# Python program to generate all the subse-quence # starting with vowel and ending with consonant. # Set to store all the subsequences st = set () # Utility method to check vowel def isVowel(c): return (c = = 'a' or c = = 'e' or c = = 'i' or c = = 'o' or c = = 'u' ) # Utility method to check consonant def isConsonant(c): return not isVowel(c) # It computes all the possible substring that # starts with vowel and end with consonant def subsequence( Str ): global st # iterate over the entire string for i in range ( len ( Str )): # test ith character for vowel if (isVowel( Str [i])): # if the ith character is vowel # iterate from end of the string # and check for consonant. for j in range ( len ( Str ) - 1 ,i - 1 , - 1 ): # test jth character for consonant. if (isConsonant( Str [j])): # once we get a consonant add it to # the hashset str_sub = Str [i : i + j + 1 ] st.add(str_sub) # drop each character of the substring # and recur to generate all subsequence # of the substring for k in range ( 1 , len (str_sub)): sb = str_sub sb = sb.replace(sb[k],"") subsequence(sb) # Driver Code s = "xabcef" subsequence(s) for i in st: print (i,end = " " ) print () # This code is contributed by shinjanpatra |
C#
// C# Program to generate all the subsequence // starting with vowel and ending with consonant. using System; using System.Collections.Generic; using System.Text; class Subsequence { // Set to store all the subsequences static HashSet<String> st = new HashSet<String>(); // It computes all the possible substring that // starts with vowel and end with consonant static void subsequence(String str) { // iterate over the entire string for ( int i = 0; i < str.Length; i++) { // test ith character for vowel if (isVowel(str[i])) { // if the ith character is vowel // iterate from end of the string // and check for consonant. for ( int j = (str.Length - 1); j >= i; j--) { // test jth character for consonant. if (isConsonant(str[j])) { // once we get a consonant add it to // the hashset String str_sub = str.Substring(i, j -i + 1); st.Add(str_sub); // drop each character of the substring // and recur to generate all subsequence // of the substring for ( int k = 1; k < str_sub.Length - 1; k++) { StringBuilder sb = new StringBuilder(str_sub); sb.Remove(k, 1); subsequence(sb.ToString()); } } } } } } // Utility method to check vowel static bool isVowel( char c) { return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ); } // Utility method to check consonant static bool isConsonant( char c) { return !isVowel(c); } // Driver code public static void Main(String[] args) { String s = "xabcef" ; subsequence(s); foreach (String str in st) Console.Write(str + ", " ); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program to generate all the subse-quence // starting with vowel and ending with consonant. // Set to store all the subsequences let st = new Set(); // Utility method to check vowel function isVowel(c) { return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ); } // Utility method to check consonant function isConsonant(c) { return !isVowel(c); } // It computes all the possible substring that // starts with vowel and end with consonant function subsequence(str) { // iterate over the entire string for (let i = 0; i < str.length; i++) { // test ith character for vowel if (isVowel(str[i])) { // if the ith character is vowel // iterate from end of the string // and check for consonant. for (let j = str.length - 1; j >= i; j--) { // test jth character for consonant. if (isConsonant(str[j])) { // once we get a consonant add it to // the hashset let str_sub = str.substring(i, i + j + 1); st.add(str_sub); // drop each character of the substring // and recur to generate all subsequence // of the substring for (let k = 1; k < str_sub.length - 1; k++) { let sb = str_sub; sb = sb.replace(sb[k], "" ); subsequence(sb); } } } } } } // Driver Code let s = "xabcef" ; subsequence(s); for (let i of st) document.write(i, " " ); document.write( "</br>" ); // This code is contributed by shinjanpatra </script> |
ab abc abce abcef abcf abef abf ac acef acf aef af ef
Time complexity: O(2^n) where n is the length of the string
Auxiliary space: O(2^n)
Print all Subsequences of String which Start with Vowel and End with Consonant.
Given a string return all possible subsequences which start with a vowel and end with a consonant. A String is a subsequence of a given String, that is generated by deleting some character of a given string without changing its order.
Examples:
Input : 'abc'
Output : ab, ac, abc
Input : 'aab'
Output : ab, aab
Question Source: Yatra.com Interview Experience | Set 7