Given a string return all unique possible subsequences which start with vowel and end with 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.
NOTE: Return all the unique subsequences in lexicographically sorted order. 
Example 1:
Input: S = "abc"
Output: "ab", "ac", "abc" 
Explanation: "ab", "ac", "abc" are 
the all possible subsequences which 
start with vowel and end with consonant.
Example 2:
Input: S = "aab"
Output: "ab", "aab"
Explanation: "ab", "aab" are the all 
possible subsequences which start 
with vowel and end with consonant.
Your Task:  
You dont need to read input or print anything. Complete the function allPossileSubsequences() which takes S as input parameter and returns all possible subsequences which start with vowel and end with consonant.
Expected Time Complexity: O(n*logn*2^{n})
Expected Auxiliary Space: O(2^{n})
Constraints:
1<= |S| <=18

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:

    def allPossibleSubsequences (ob, S):

        # code here 



Solutions:
class Solution:

	def allPossibleSubsequences(ob, s):
		a = []
		dic = {}
		(dic['a'], dic['e'], dic['i'], dic['o'], dic['u']) = (1, 1, 1, 1, 1)

		def manu(i, t, s):
			if i == len(s):
				if t and t[-1] not in dic:
					a.append(t)
				return
			if len(t) == 0:
				if s[i] in dic:
					manu(i + 1, t + s[i], s)
				manu(i + 1, t, s)
			else:
				manu(i + 1, t + s[i], s)
				manu(i + 1, t, s)
		manu(0, '', s)
		return sorted(list(set(a)))


class Solution:

	def solve(self, ans, tmp, i, s):
		if i == len(s):
			ans.append(''.join(tmp))
			return
		self.solve(ans, tmp, i + 1, s)
		tmp.append(s[i])
		self.solve(ans, tmp, i + 1, s)
		tmp.pop()

	def allPossibleSubsequences(self, S):
		ans = []
		tmp = []
		self.solve(ans, tmp, 0, S)
		res = set()
		vowel = ['a', 'e', 'i', 'o', 'u']
		consonent = [i for i in 'bcdfghjklmnpqrstvwxyz']
		for i in ans:
			if i == '' or len(i) == 1:
				continue
			if i[0] in vowel and i[-1] in consonent:
				res.add(i)
		res = list(res)
		return sorted(res)


class Solution:

	def solve(ob, S, ans, output, index):
		if index >= len(S):
			if output and output[0] in 'aeiou' and (output[-1] not in 'aeiou'):
				ans.append(output)
			return
		ob.solve(S, ans, output, index + 1)
		output = output + S[index]
		ob.solve(S, ans, output, index + 1)

	def allPossibleSubsequences(ob, S):
		ans = []
		output = ''
		index = 0
		ob.solve(S, ans, output, index)
		s = set(ans)
		l = list(s)
		l.sort()
		return l


class Solution:

	def allPossibleSubsequences(ob, S):
		vowel = {'a', 'e', 'i', 'o', 'u'}
		arr = set()
		temp = []
		ob.Util(0, S, arr, temp, vowel)
		arr = list(arr)
		arr.sort()
		return arr

	def Util(self, index, S, arr, temp, vowel):
		if index == len(S):
			if len(temp) > 0 and temp[0] in vowel and (temp[-1] not in vowel):
				arr.add(''.join(temp))
			return
		temp.append(S[index])
		self.Util(index + 1, S, arr, temp, vowel)
		del temp[-1]
		self.Util(index + 1, S, arr, temp, vowel)


class Solution:

	def allPossibleSubsequences(ob, s):
		sequences = set()
		for i in range(2 ** len(s)):
			temp = ''
			for j in range(len(s)):
				if i & 1 << j:
					temp += s[j]
			sequences.add(temp)
		sequences = list(sequences)
		sequences.sort()
		result = []
		for item in sequences:
			if len(item) > 1:
				if item[0] == 'a' or item[0] == 'e' or item[0] == 'i' or (item[0] == 'o') or (item[0] == 'u'):
					if item[-1] == 'a' or item[-1] == 'e' or item[-1] == 'i' or (item[-1] == 'o') or (item[-1] == 'u'):
						continue
					else:
						result.append(item)
		return result


class Solution:
	les = []
	vowel = {'a', 'e', 'i', 'o', 'u'}

	def fun(ob, t, i, n, s):
		if i == n:
			if len(t) != 0 and t[0] in ob.vowel and (t[-1] not in ob.vowel):
				ob.les.append(t)
		else:
			ob.fun(t, i + 1, n, s)
			t = t + s[i]
			ob.fun(t, i + 1, n, s)

	def allPossibleSubsequences(ob, S):
		ob.les = []
		ob.fun('', 0, len(S), S)
		l = list(set(ob.les))
		l.sort()
		return l


class Solution:

	def allPossibleSubsequences(ob, S):
		vowel = 'aeiou'
		ans = set()
		n = len(S)
		tot = 2 ** n
		for i in range(tot):
			temp = ''
			for j in range(n):
				if temp and temp[0] not in vowel:
					break
				if i & 1 << j:
					temp += S[j]
			if temp and temp[0] in vowel and (temp[-1] not in vowel):
				ans.add(temp)
		return sorted(ans)


class Solution:

	def allPossibleSubsequences(ob, S):
		vowel = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
		out = {}
		ob.helper(S, 0, out, '', vowel)
		return sorted(out.keys())

	def helper(self, s, i, out, temp, vowel):
		if i >= len(s):
			if len(temp) >= 2 and temp[-1] not in vowel and (temp not in out):
				out[temp] = 1
			return
		if temp:
			z = temp + s[i]
			self.helper(s, i + 1, out, z, vowel)
			self.helper(s, i + 1, out, temp, vowel)
		elif s[i] in vowel:
			z = temp + s[i]
			self.helper(s, i + 1, out, z, vowel)
			self.helper(s, i + 1, out, temp, vowel)
		else:
			self.helper(s, i + 1, out, temp, vowel)
		return


class Solution:

	def seq(self, S, o, a, i):
		if i == len(S):
			a.append(o)
			return
		self.seq(S, o, a, i + 1)
		o += S[i]
		self.seq(S, o, a, i + 1)

	def allPossibleSubsequences(self, S):
		S = S
		i = 0
		o = ''
		a = []
		s = []
		vowel = ['a', 'e', 'i', 'o', 'u']
		self.seq(S, o, a, i)
		j = 0
		a = list(set(a))
		a.sort()
		while j < len(a):
			if len(a[j]) > 1 and a[j][0] in vowel and (a[j][-1] not in vowel):
				s.append(a[j])
				j += 1
			else:
				j += 1
		return s


class Solution:

	def allPossibleSubsequences(ob, S):

		def spring(S, lst, i, n, pat):
			if i == n:
				if pat and pat[0] in 'aeiou' and (pat[-1] not in 'aeiou'):
					lst.add(pat)
				return
			spring(S, lst, i + 1, n, pat)
			spring(S, lst, i + 1, n, pat + S[i])
		lst = set()
		i = 0
		n = len(S)
		spring(S, lst, i, n, '')
		return sorted(list(lst))


class Solution:

	def allPossibleSubsequences(ob, S):
		vowels = 'aeiou'

		def subs(arr, out, res):
			if len(out) >= 2:
				if out[0] in vowels and out[-1] not in vowels:
					res.append(out)
			if len(arr) == 0:
				return
			subs(arr[1:], out, res)
			subs(arr[1:], out + arr[0], res)
			return
		res = []
		out = ''
		subs(S, out, res)
		res = list(set(res))
		return sorted(res)


class Solution:

	def allPossibleSubsequences(ob, S):
		answer = []
		string = list(S)

		def recursion(index, string, temp):
			if index == len(string):
				temp1 = []
				for i in temp:
					temp1.append(i)
				answer.append(temp1)
				return
			recursion(index + 1, string, temp)
			temp.append(string[index])
			recursion(index + 1, string, temp)
			temp.pop()
		temp = []
		recursion(0, string, temp)
		sample = []
		hashset = set()
		for i in answer:
			value = ''.join(i)
			if value not in hashset:
				sample.append(value)
				hashset.add(value)
		output = []
		hashset_vowels = set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])
		for i in sample:
			if len(i) < 2:
				continue
			else:
				first = i[0]
				last = i[-1]
				if first in hashset_vowels and last not in hashset_vowels:
					output.append(i)
		output.sort()
		return output


class Solution:

	def allPossibleSubsequences(ob, S):
		N = len(S)
		ans = []
		X = 2 ** N
		for i in range(1, X):
			curr = ''
			start = -1
			for j in range(N):
				if i & 1 << j:
					if start == -1 and S[j] not in 'aeiou':
						break
					start = 1
					curr += S[j]
			if len(curr) > 1 and curr[0] in 'aeiou' and (curr[-1] not in 'aeiou'):
				ans.append(curr)
		ans = list(set(ans))
		return sorted(ans)


class Solution:

	def allPossibleSubsequences(ob, s):
		ans = []
		vowels = ('a', 'e', 'i', 'o', 'u')

		def sol(s, i, n, path):
			if i == n:
				string = ''
				for i in path:
					string += i
				if string and string[0] in vowels and (string[-1] not in vowels):
					ans.append(string)
				return
			path.append(s[i])
			sol(s, i + 1, n, path)
			path.pop()
			sol(s, i + 1, n, path)
			return
		sol(s, 0, len(s), [])
		return sorted(set(ans))


import sys
sys.setrecursionlimit(10000)

class Solution:

	def allPossibleSubsequences(self, s):
		ans = []
		vowels = ('a', 'e', 'i', 'o', 'u')

		def sol(s, n, i, path):
			if i == n:
				string = ''
				for i in path:
					string += i
				if string and string[0] in vowels and (string[-1] not in vowels):
					ans.append(string)
				return
			path.append(s[i])
			sol(s, n, i + 1, path)
			path.pop()
			sol(s, n, i + 1, path)
			return
		sol(s, len(s), 0, [])
		return sorted(set(ans))


class Solution:

	def allPossibleSubsequences(ob, s):
		l = [bin(i)[2:] for i in range(1, 2 ** len(s))]
		sub_seq = []
		for num in l:
			S = ''
			for i in range(-1, -len(num) - 1, -1):
				if num[i] == '1':
					S = s[i] + S
			sub_seq.append(S)
		v = ['a', 'e', 'i', 'o', 'u']
		res = []
		for s in sub_seq:
			if s[0] in v and s[-1] not in v:
				res.append(s)
		res = set(res)
		return sorted(res)


class Solution:

	def allPossibleSubsequences(ob, s):
		n = len(s)
		new = []
		for i in range(1, 2 ** n):
			temp = bin(i)[2:]
			S = ''
			for i in range(-1, -len(temp) - 1, -1):
				if temp[i] == '1':
					S = s[i] + S
			new.append(S)
		vowel = 'aeiou'
		result = []
		for elm in new:
			if elm[0] in vowel and elm[-1] not in vowel:
				result.append(elm)
		result = set(result)
		result = list(result)
		result.sort()
		return result


class Solution:

	def allPossibleSubsequences(ob, S):
		ans = set()
		vow = set()
		vow.add('a')
		vow.add('e')
		vow.add('i')
		vow.add('o')
		vow.add('u')
		n = len(S)

		def subs(i, S, ans, cur, vow, n):
			if i == n:
				if len(cur) > 0:
					if cur[0] in vow and cur[-1] not in vow and (len(cur) > 1):
						ans.add(cur)
				return
			subs(i + 1, S, ans, cur, vow, n)
			if i == 0:
				subs(i + 1, S, ans, S[i], vow, n)
			else:
				subs(i + 1, S, ans, cur + S[i], vow, n)
		subs(0, S, ans, '', vow, n)
		return sorted(list(ans))


class Solution:

	def allPossibleSubsequences(ob, s):
		res = set()

		def fun(ind, st):
			if ind >= len(s):
				if len(st) >= 2 and st[0] in ['a', 'e', 'i', 'o', 'u'] and (st[-1] not in ['a', 'e', 'i', 'o', 'u']):
					res.add(st)
				return
			fun(ind + 1, st + s[ind])
			fun(ind + 1, st)
		fun(0, '')
		return sorted(list(res))


class Solution:

	def subsequence(ob, S):
		if len(S) == 0:
			l = []
			l.append('')
			return l
		smalloutput = ob.subsequence(S[1:])
		newlist = []
		newlist.extend(smalloutput)
		for i in smalloutput:
			result = S[0] + i
			newlist.append(result)
		return newlist

	def allPossibleSubsequences(ob, S):
		result = set()
		nl = ob.subsequence(S)
		for i in nl:
			if len(i) > 1:
				if i[0] in ('a', 'e', 'i', 'o', 'u') and i[-1] not in ('a', 'e', 'i', 'o', 'u'):
					result.add(i)
		output = []
		output.extend(result)
		output.sort()
		return output


class Solution:

	def solve(ob, arr, index, ans, output):
		if index >= len(arr):
			output.append(ans[:])
			return
		ans.append(arr[index])
		ob.solve(arr, index + 1, ans, output)
		ans.pop()
		ob.solve(arr, index + 1, ans, output)
		return output

	def allPossibleSubsequences(ob, S):
		output = []
		ans = []
		arr = list(S)
		index = 0
		vowel = ['a', 'e', 'i', 'o', 'u']
		fin_ans = ob.solve(arr, index, ans, output)
		temp = []
		fin_ans.sort()
		for i in fin_ans:
			if len(i) > 0 and i[0] in vowel and (i[-1] not in vowel):
				return_ans = ''.join([str(elem) for elem in i])
				temp.append(return_ans)
		temp = list(set(temp))
		temp.sort()
		return temp


from itertools import combinations

class Solution:

	def allPossibleSubsequences(ob, S):
		v = {}
		c = {}
		vv = 'aeiou'
		cc = 'bcdfghjklmnpqrstvwxyz'
		for i in vv:
			v[i] = 1
		for i in cc:
			c[i] = 1
		ans = []
		for i in range(2, len(S) + 1):
			for j in combinations(S, i):
				if j[0] in v and j[-1] in c:
					ans.append(''.join(j))
		return sorted(set(ans))


class Solution:

	def allPossibleSubsequences(ob, S):
		l = []
		l1 = []
		vowels = 'aeiou'

		def printall(ind, l):
			if ind >= len(S):
				if len(l) > 1 and l[0] in vowels and (l[-1] not in vowels):
					l1.append(''.join(l))
				return
			l.append(S[ind])
			printall(ind + 1, l)
			l.pop()
			printall(ind + 1, l)
		printall(0, l)
		l1 = list(set(l1))
		l1.sort()
		return l1


class Solution:

	def allPossibleSubsequences(self, S):
		vowel = {'a', 'e', 'i', 'o', 'u'}
		sub = []
		ans = []

		def bt(i):
			if i == len(S):
				if len(sub) != 0:
					ans.append(''.join(sub))
				return
			sub.append(S[i])
			bt(i + 1)
			sub.pop()
			bt(i + 1)
		bt(0)
		res = []
		for i in ans:
			if i[0] in vowel and i[-1] not in vowel:
				res.append(i)
		return sorted(list(set(res)))


class Solution:

	def solve(self, i, o):
		if len(i) == 0:
			if len(o) != 0 and o[0] in 'aeiou' and (o[-1] not in 'aeiou'):
				self.l.append(o)
			return
		o1 = o
		o2 = o + i[0]
		i = i[1:]
		self.solve(i, o1)
		self.solve(i, o2)
		return

	def allPossibleSubsequences(self, s):
		self.l = []
		n = len(s)
		i = s
		o = ''
		self.solve(i, o)
		ans = list(set(self.l))
		ans.sort()
		return ans


class Solution:

	def allPossibleSubsequences(ob, S):
		li = []
		v = ['a', 'e', 'i', 'o', 'u']

		def subseq(S, i, t):
			if i == len(S):
				if len(t) > 1:
					if t[0] in v and t[-1] not in v:
						li.append(t)
				return
			p = S[i]
			subseq(S, i + 1, t + p)
			subseq(S, i + 1, t)
		subseq(S, 0, '')
		li = list(set(li))
		li.sort()
		return li


class Solution:

	def allPossibleSubsequences(ob, S):
		res = set()
		vowel = ['a', 'e', 'i', 'o', 'u']

		def solve(i, val):
			if i == len(S):
				x = val[:]
				if x and x[0] in vowel and (x[-1] not in vowel):
					res.add(''.join(x))
				return
			solve(i + 1, val + [S[i]])
			solve(i + 1, val)
		solve(0, [])
		res = list(res)
		return sorted(res)


class Solution:

	def is_valid(self, ans):
		vols = ['a', 'e', 'i', 'o', 'u']
		if ans[0] in vols and ans[-1] not in vols:
			return True
		return False

	def all_subsets(self, st, ans, res):
		if not st:
			if len(ans) > 1 and self.is_valid(ans):
				res.add(ans)
			return
		self.all_subsets(st[1:], ans + st[0], res)
		self.all_subsets(st[1:], ans, res)

	def allPossibleSubsequences(ob, s):
		res = set()
		ob.all_subsets(s, '', res)
		return sorted(res)


class Solution:

	def allPossibleSubsequences(ob, S):
		s = set(['a', 'e', 'i', 'o', 'u'])

		def prinK(S):
			if not S:
				return []
			elif len(S) == 1:
				return [S[0]]
			else:
				ans = []
				a = S[0]
				ans.append(a)
				r = prinK(S[1:])
				for i in r:
					ans.append(a + i)
				for i in r:
					ans.append(i)
				return ans
		res = set()
		for i in prinK(S):
			if i[0] in s and i[-1] not in s:
				res.add(i)
		return sorted(list(res))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ans = set()
		ob = Solution()
		ans = ob.allPossibleSubsequences(S)
		if len(ans) == 0:
			print(-1, end='')
		else:
			for i in ans:
				print(i, end=' ')
		print()


class Solution:

	def allPossibleSubsequences(ob, S):
		output = []

		def solver(inx, s, temp):
			if inx == len(s):
				return
			output.append(temp + s[inx])
			solver(inx + 1, s, temp + s[inx])
			output.append(temp)
			solver(inx + 1, s, temp)
		solver(0, S, '')
		realout = []
		output = set(output)
		output = list(output)
		vowels = ['a', 'e', 'i', 'o', 'u']
		for i in output:
			if i != '':
				if i[0] in vowels:
					if i[-1] not in vowels:
						realout.append(i)
		realout.sort()
		return realout
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ans = set()
		ob = Solution()
		ans = ob.allPossibleSubsequences(S)
		if len(ans) == 0:
			print(-1, end='')
		else:
			for i in ans:
				print(i, end=' ')
		print()


class Solution:

	def allPossibleSubsequences(ob, S):
		n = len(S)
		ans = []
		vowels = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
		visited = [0 for i in range(n)]
		dec = {}

		def find(index, string):
			if index == n:
				return 0
			if not vowels.get(S[index]):
				dec[string + S[index]] = 1
			return find(index + 1, string) or find(index + 1, string + S[index])
		for i in range(n):
			if vowels.get(S[i]):
				find(i + 1, S[i])
		ans = [i for i in dec]
		ans.sort()
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ans = set()
		ob = Solution()
		ans = ob.allPossibleSubsequences(S)
		if len(ans) == 0:
			print(-1, end='')
		else:
			for i in ans:
				print(i, end=' ')
		print()


from collections import defaultdict

class Solution:

	def allPossibleSubsequences(ob, S):
		n = len(S)
		vowels = 'a,e,i,o,u'
		vowels = set(vowels)
		res = []
		Set = set()

		def helper(i, path):
			if i == n:
				if path and path[0] in vowels and (path[-1] not in vowels) and (path not in Set):
					res.append(path)
					Set.add(path)
				return
			helper(i + 1, path + S[i])
			helper(i + 1, path)
		helper(0, '')
		res.sort()
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ans = set()
		ob = Solution()
		ans = ob.allPossibleSubsequences(S)
		if len(ans) == 0:
			print(-1, end='')
		else:
			for i in ans:
				print(i, end=' ')
		print()


class Solution:

	def allPossibleSubsequences(self, S):
		l = []
		c = ''
		nl = []
		self.subs(S, 0, c, l)
		for i in l:
			if len(i) > 0:
				if (i[0] == 'a' or i[0] == 'e' or i[0] == 'i' or (i[0] == 'o') or (i[0] == 'u')) and (i[-1] != 'a' and i[-1] != 'e' and (i[-1] != 'i') and (i[-1] != 'o') and (i[-1] != 'u')):
					nl.append(i)
		fl = set(nl)
		nl = list(fl)
		nl.sort()
		return nl

	def subs(self, S, i, c, l):
		if i == len(S):
			l.append(c)
			return
		self.subs(S, i + 1, c + S[i], l)
		self.subs(S, i + 1, c, l)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ans = set()
		ob = Solution()
		ans = ob.allPossibleSubsequences(S)
		if len(ans) == 0:
			print(-1, end='')
		else:
			for i in ans:
				print(i, end=' ')
		print()


class Solution:

	def allPossibleSubsequences(ob, s):
		res = set()

		def vow(a):
			if a == 'a' or a == 'e' or a == 'i' or (a == 'o') or (a == 'u'):
				return True
			return False

		def helper(i, st):
			if i >= len(s):
				return
			if len(st) == 0:
				if vow(s[i]):
					helper(i + 1, s[i])
				helper(i + 1, '')
			else:
				if not vow(s[i]):
					res.add(st + s[i])
				helper(i + 1, st + s[i])
				helper(i + 1, st)
		helper(0, '')
		return sorted(list(res))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ans = set()
		ob = Solution()
		ans = ob.allPossibleSubsequences(S)
		if len(ans) == 0:
			print(-1, end='')
		else:
			for i in ans:
				print(i, end=' ')
		print()


def isVowel(c):
	vow = set('aeiouAEIOU')
	if c in vow:
		return True
	return False

class Solution:

	def aps(self, s, op, l):
		if len(s) == 0:
			if op and isVowel(op[0]) and (not isVowel(op[-1])):
				l.add(op)
			return l
		l = self.aps(s[1:], op + s[0], l)
		l = self.aps(s[1:], op, l)
		return l

	def allPossibleSubsequences(ob, S):
		l = set()
		op = ''
		l = ob.aps(S, op, l)
		return sorted(l)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ans = set()
		ob = Solution()
		ans = ob.allPossibleSubsequences(S)
		if len(ans) == 0:
			print(-1, end='')
		else:
			for i in ans:
				print(i, end=' ')
		print()


def isVowel(ch):
	S = set('aeiouAEIOU')
	if ch in S:
		return True
	return False

class Solution:

	def allPossibleSubsequences(self, S):
		n = len(S)
		s = set()
		for i in range(1 << n):
			sub = ''
			for j in range(n):
				if 1 << j & i:
					sub += S[j]
			if sub and isVowel(sub[0]) and (not isVowel(sub[-1])):
				s.add(sub)
		return sorted(set(s))