Given a string S, sort it in the following manner. Sorted string must contain a vowel as first letter and a consonant as next letter and so on OR a consonant as first letter and a vowel as next letter and so on, depending on the string. If there is no vowel left then print the remaining consonant in ascending order and vice versa. 
Note: Order of vowel must be a->e->i->o->u and order of consonant must be b->c->d... and so on.
Example 1: 
Input: abcdei 
Output: abecid 
Explanation: 'a' (Vowel) came first so the
pattern of sorted string is vcvcvcvc... 
Example 2: 
Input: bcadefgh
Output: bacedfgh 
Explanation: 'b' (consonant) came first so
the pattern of sorted string is cvcvcvcv....
 
Your Task: 
You don't need to read input or print anything. Your task is to complete the function SortedString() which takes the string s as input parameters and returns the sorted string. 
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1<=|S|<=1000000

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3


class Solution:
    def SortedString(self, s:str) -> str:
        # code here

Solutions:
class Solution:

	def SortedString(self, s: str) -> str:
		v = 'aeiou'
		vowels = ''
		cons = ''
		for i in s:
			if i in v:
				vowels += i
			else:
				cons += i
		res = ''
		vowels = sorted(vowels)
		cons = sorted(cons)
		if len(vowels) < len(cons):
			for j in range(len(vowels)):
				if s[0] in v:
					res += vowels[j] + cons[j]
				else:
					res += cons[j] + vowels[j]
			for j in range(len(vowels), len(cons)):
				res += cons[j]
		elif len(cons) < len(vowels):
			for k in range(len(cons)):
				if s[0] in v:
					res += vowels[k] + cons[k]
				else:
					res += cons[k] + vowels[k]
			for k in range(len(cons), len(vowels)):
				res += vowels[k]
		elif len(vowels) == len(cons):
			for i in range(len(vowels)):
				if s[0] in v:
					res += vowels[i] + cons[i]
				else:
					res += cons[i] + vowels[i]
		return res


class Solution:

	def SortedString(self, s: str) -> str:
		v = ''
		c = ''
		s = list(s)
		t = {'a', 'e', 'i', 'o', 'u'}
		for i in s:
			if i in t:
				v += i
			else:
				c += i
		v = sorted(v)
		c = sorted(c)
		p = 0
		k = 0
		f = 0
		if s[0] in t:
			f = 1
		for i in range(len(s)):
			if p >= len(v):
				s[i] = c[k]
				k += 1
			elif k >= len(c):
				s[i] = v[p]
				p += 1
			elif i % 2 == 0:
				if f:
					s[i] = v[p]
					p += 1
				else:
					s[i] = c[k]
					k += 1
			elif f:
				s[i] = c[k]
				k += 1
			else:
				s[i] = v[p]
				p += 1
		s = ''.join(s)
		return s


class Solution:

	def SortedString(self, s: str) -> str:
		vowels = set('aeiou')
		arr = []
		brr = []
		for item in s:
			if item in vowels:
				arr.append(item)
			else:
				brr.append(item)
		arr.sort(reverse=True)
		brr.sort(reverse=True)
		output = ''
		if s[0] not in vowels:
			output += brr.pop()
		while arr and brr:
			output += arr.pop() + brr.pop()
		while arr:
			output += arr.pop()
		while brr:
			output += brr.pop()
		return output


class Solution:

	def SortedString(self, s: str) -> str:
		d1 = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
		sort1 = ''
		sort2 = ''
		alt = ''
		for i in s:
			if i in d1:
				sort1 += i
			else:
				sort2 += i
		vowel = ''.join(sorted(sort1))
		cons = ''.join(sorted(sort2))
		if s[0] in d1:
			(i, j) = (0, 0)
			while i < len(vowel) and j < len(cons):
				alt += vowel[i]
				alt += cons[j]
				i += 1
				j += 1
			if len(cons[j:]) > 0:
				return alt + cons[j:]
			else:
				return alt
		else:
			(i, j) = (0, 0)
			while i < len(vowel) and j < len(cons):
				alt += cons[j]
				alt += vowel[i]
				i += 1
				j += 1
			if len(cons[j:]) > 0:
				return alt + cons[j:]
			else:
				return alt


class Solution:

	def SortedString(self, s: str) -> str:
		vowels = []
		consonants = []
		for i in range(len(s)):
			if s[i] in 'aeiou':
				vowels.append(s[i])
			else:
				consonants.append(s[i])
		vowels.sort()
		consonants.sort()
		vowels = ''.join(vowels)
		consonants = ''.join(consonants)
		a = 0
		b = 0
		res = ''
		turn = ''
		while a < len(vowels) and b < len(consonants):
			if res == '' and s[0] in 'aeiou':
				res += vowels[a]
				a += 1
				turn = 'c'
			elif res == '' and s[0] not in 'aeiou':
				res += consonants[b]
				b += 1
				turn = 'v'
			elif turn == 'c':
				res += consonants[b]
				b += 1
				turn = 'v'
			else:
				res += vowels[a]
				a += 1
				turn = 'c'
		if a < len(vowels):
			res += vowels[a:]
			return res
		elif b < len(consonants):
			res += consonants[b:]
			return res
		else:
			return res


class Solution:

	def SortedString(self, s: str) -> str:
		s = s.lower()
		la = sorted(s)
		vowels = ['a', 'e', 'i', 'o', 'u']
		sv = [ele for ele in la if ele in vowels]
		sc = [ele for ele in la if ele not in vowels]
		sf = ''
		if s[0] in vowels:
			flag = 0
		else:
			flag = 1
		while len(sv) != 0 or len(sc) != 0:
			if flag == 0:
				if len(sv) != 0:
					tmp = sv.pop(0)
					sf += tmp
				flag = 1
			elif flag == 1:
				if len(sc) != 0:
					tmp = sc.pop(0)
					sf += tmp
				flag = 0
		return sf


class Solution:

	def SortedString(self, s: str) -> str:
		vowel = []
		conso = []
		v = ['a', 'e', 'i', 'o', 'u']
		if s[0] in v:
			vow_first = True
		else:
			vow_first = False
		for i in s:
			if i in v:
				vowel.append(i)
			else:
				conso.append(i)
		vowel.sort()
		conso.sort()
		(n, m) = (len(vowel), len(conso))
		res = [None] * (n + m)
		(i, j, k) = (0, 0, 0)
		if vow_first:
			while j < n and k < m:
				if i % 2 == 0:
					res[i] = vowel[j]
					j += 1
					i += 1
				else:
					res[i] = conso[k]
					k += 1
					i += 1
		else:
			while j < m and k < n:
				if i % 2 == 0:
					res[i] = conso[j]
					j += 1
					i += 1
				else:
					res[i] = vowel[k]
					k += 1
					i += 1
		if vow_first:
			while j < n:
				res[i] = vowel[j]
				j += 1
				i += 1
			while k < m:
				res[i] = conso[k]
				k += 1
				i += 1
		else:
			while j < m:
				res[i] = conso[j]
				j += 1
				i += 1
			while k < n:
				res[i] = vowel[k]
				k += 1
				i += 1
		return ''.join(res)


class Solution:

	def SortedString(self, s: str) -> str:
		v = []
		c = []
		res = 'aeiou'
		for i in s:
			if i in res:
				v.append(i)
			else:
				c.append(i)
		v.sort()
		c.sort()
		ans = ''
		if s[0] in v:
			for i in range(len(s)):
				if i < len(v):
					ans += v[i]
				if i < len(c):
					ans += c[i]
		else:
			for i in range(len(s)):
				if i < len(c):
					ans += c[i]
				if i < len(v):
					ans += v[i]
		return ans


class Solution:

	def SortedString(self, s: str) -> str:
		vowels = []
		consonants = []
		for i in s:
			if i == 'a' or i == 'e' or i == 'i' or (i == 'o') or (i == 'u'):
				vowels.append(i)
			else:
				consonants.append(i)
		vowels.sort()
		consonants.sort()
		ans = ''
		if s[0] == 'a' or s[0] == 'e' or s[0] == 'i' or (s[0] == 'o') or (s[0] == 'u'):
			while len(vowels) != 0 and len(consonants) != 0:
				ans += vowels[0]
				ans += consonants[0]
				vowels.pop(0)
				consonants.pop(0)
			while len(vowels) != 0:
				ans += vowels[0]
				vowels.pop(0)
			while len(consonants) != 0:
				ans += consonants[0]
				consonants.pop(0)
		else:
			while len(vowels) != 0 and len(consonants) != 0:
				ans += consonants[0]
				ans += vowels[0]
				vowels.pop(0)
				consonants.pop(0)
			while len(vowels) != 0:
				ans += vowels[0]
				vowels.pop(0)
			while len(consonants) != 0:
				ans += consonants[0]
				consonants.pop(0)
		return ans