Given a string S of lowercase english characters. Rearrange characters of the given string such that the vowels and consonants occupy alternate positions and the string so formed should be lexicographically (alphabetically) smallest. 
Note: Vowels are 'a', 'e', 'i', 'o' and 'u'. 
Example 1:
Input:
S = "aeroplane"
Output: alanepero
Explanation: alanepero  
The vowels and consonants are arranged 
alternatively with vowels shown in bold.
Also, there's no lexicographically smaller
string possible with required conditions.
Example 2:
Input: 
S = "mississippi"
Output: -1
Explanation: The number of vowels is 4 
whereas the number of consonants is 7.
Hence, there's no way to arrange the
vowels and consonants alternatively.
Your Task:
You don't need to read input or print anything. Your task is to complete the function rearrange() which takes the string S and its size N as inputs and returns the modified string as stated in the description. If such a modification is not possible, return the string "-1".
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(2*26).
Constraints:
1 <= N <= 10^6
'a' <= S[ i ] <= 'z'

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(2*26).

Starter code:
#User function Template for python3



class Solution:

    def rearrange(self, S, N):

        # code here

        

Solutions:
class Solution:

	def rearrange(self, S, N):
		if N == 1:
			return S
		vs = {'a', 'e', 'i', 'o', 'u'}
		va = []
		ca = []
		S = sorted(S)
		for ch in S:
			if ch in vs:
				va.append(ch)
			else:
				ca.append(ch)
		if len(va) == len(ca) or len(va) == len(ca) + 1 or len(va) + 1 == len(ca):
			if len(va) < len(ca):
				small = va
				big = ca
			elif len(va) > len(ca):
				small = ca
				big = va
			elif va[0] > ca[0]:
				big = ca
				small = va
			else:
				big = va
				small = ca
			i = 0
			bi = 0
			si = 0
			new_s = ''
			while i < len(S):
				if i % 2 == 0:
					new_s += big[bi]
					bi += 1
				else:
					new_s += small[si]
					si += 1
				i += 1
			return new_s
		else:
			return -1
		return ''


class Solution:

	def rearrange(self, S, N):
		S = list(S)
		S.sort()
		vow = []
		con = []
		s = ['a', 'e', 'i', 'o', 'u']
		ss = set(s)
		for i in range(len(S)):
			if S[i] in ss:
				vow.append(S[i])
			else:
				con.append(S[i])
		res = ''
		maxi = max(vow, con, key=len)
		mini = min(vow, con, key=len)
		if len(maxi) == len(mini):
			maxi1 = max(vow, con)
			mini1 = min(vow, con)
			for i in range(len(mini)):
				res += mini1[i]
				res += maxi1[i]
		elif len(maxi) == len(mini) + 1:
			for i in range(len(mini)):
				res += maxi[i]
				res += mini[i]
			res += maxi[i + 1]
		else:
			return -1
		return res


class Solution:

	def form(self, s1, n, s2, m):
		(i, j, flag) = (0, 0, 1)
		ans = ''
		while i < n and j < m:
			if flag:
				ans += s1[i]
				i += 1
				flag = 0
			else:
				ans += s2[j]
				j += 1
				flag = 1
		if i < n:
			ans += s1[i]
		if j < m:
			ans += s2[j]
		return ans

	def rearrange(self, s, N):
		if N == 1:
			return s
		(vowel, conso) = (0, 0)
		arr = [0] * 26
		for i in range(N):
			if s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
				vowel += 1
			else:
				conso += 1
			arr[ord(s[i]) - 97] += 1
		if abs(vowel - conso) > 1:
			return '-1'
		(v, c) = ('', '')
		for i in range(26):
			tmp = chr(i + 97)
			for j in range(arr[i]):
				if tmp == 'a' or tmp == 'e' or tmp == 'i' or (tmp == 'o') or (tmp == 'u'):
					v += tmp
				else:
					c += tmp
		ans = ''
		if vowel > conso or (vowel == conso and v[0] < c[0]):
			ans = self.form(v, vowel, c, conso)
		else:
			ans = self.form(c, conso, v, vowel)
		return ans


class Solution:

	def rearrange(self, S, N):
		li = ['a', 'e', 'i', 'o', 'u']
		vowel = []
		conso = []
		for ch in S:
			if ch in li:
				vowel.append(ch)
			else:
				conso.append(ch)
		if abs(len(vowel) - len(conso)) > 1:
			return '-1'
		vowel.sort()
		conso.sort()
		ans = []
		i = 0
		if len(vowel) > len(conso):
			while i < len(conso):
				ans.append(vowel[i])
				ans.append(conso[i])
				i = i + 1
			ans.append(vowel[-1])
		elif len(conso) > len(vowel):
			while i < len(vowel):
				ans.append(conso[i])
				ans.append(vowel[i])
				i = i + 1
			ans.append(conso[-1])
		elif vowel[0] < conso[0]:
			while i < len(vowel):
				ans.append(vowel[i])
				ans.append(conso[i])
				i = i + 1
		else:
			while i < len(vowel):
				ans.append(conso[i])
				ans.append(vowel[i])
				i = i + 1
		return ''.join(ans)


class Solution:

	def rearrange(self, S, N):
		li = set(['a', 'e', 'i', 'o', 'u'])
		vow = []
		con = []
		S = list(S)
		S.sort()
		for ch in S:
			if ch in li:
				vow.append(ch)
			else:
				con.append(ch)
		if abs(len(vow) - len(con)) > 1:
			return '-1'
		res = ''
		i = 0
		if len(vow) > len(con):
			while i < len(con):
				res = res + vow[i]
				res = res + con[i]
				i = i + 1
			res = res + vow[-1]
		elif len(con) > len(vow):
			while i < len(vow):
				res = res + con[i]
				res = res + vow[i]
				i = i + 1
			res = res + con[-1]
		elif vow[0] < con[0]:
			while i < len(vow):
				res = res + vow[i]
				res = res + con[i]
				i = i + 1
		else:
			while i < len(vow):
				res = res + con[i]
				res = res + vow[i]
				i = i + 1
		return res


class Solution:

	def rearrange(self, s, n):
		cnt = [0] * 26
		(v, c) = ([], [])
		for i in range(n):
			cnt[ord(s[i]) - ord('a')] += 1
		for i in range(26):
			ch = chr(ord('a') + i)
			if ch in 'aeiou':
				v += [ch] * cnt[i]
			else:
				c += [ch] * cnt[i]
		if abs(len(v) - len(c)) > 1:
			return -1

		def merge(l1, l2):
			return ''.join([l1[i] + l2[i] for i in range(len(l1))])
		ans = ''
		if len(v) > len(c):
			c += ['']
			ans = merge(v, c)
		elif len(v) < len(c):
			v += ['']
			ans = merge(c, v)
		elif v[0] < c[0]:
			ans = merge(v, c)
		else:
			ans = merge(c, v)
		return ans


class Solution:

	def rearrange(self, S, N):
		vowels = 'aeiou'
		vowels_map = {}
		consonants = [0] * 26
		c = 0
		v = 0
		for i in S:
			if i not in vowels:
				consonants[ord(i) - ord('a')] += 1
				c += 1
			else:
				if i in vowels_map:
					vowels_map[i] += 1
				else:
					vowels_map[i] = 1
				v += 1
		if v < c:
			if v + 1 != c:
				return -1
		if c < v:
			if c + 1 != v:
				return -1
		cons_string = ''
		for s in range(len(consonants)):
			if chr(s + ord('a')) not in vowels_map:
				cons_string += chr(ord('a') + s) * consonants[s]
		vowel_string = ''
		for i in vowels:
			if i in vowels_map:
				vowel_string += i * vowels_map[i]
		ans = ''
		if v == c:
			if ord(vowel_string[0]) > ord(cons_string[0]):
				ans = cons_string[0] + vowel_string[0]
				for i in range(1, v):
					ans += cons_string[i] + vowel_string[i]
			else:
				ans = vowel_string[0] + cons_string[0]
				for i in range(1, v):
					ans += vowel_string[i] + cons_string[i]
		elif v + 1 == c:
			ans = cons_string[0]
			for i in range(0, v):
				ans += vowel_string[i] + cons_string[i + 1]
		else:
			ans = vowel_string[0]
			for i in range(0, c):
				ans += cons_string[i] + vowel_string[i + 1]
		return ans


from collections import deque

class Solution:

	def rearrange(self, S, N):
		if N <= 1:
			return -1
		vow = set(['a', 'e', 'i', 'o', 'u'])
		(v, c) = ([], [])
		for each in S:
			if each not in vow:
				c.append(each)
			else:
				v.append(each)
		if abs(len(v) - len(c)) > 1:
			return -1
		v.sort()
		c.sort()
		res = ''
		st = True
		if len(v) == len(c):
			if ord(v[0]) > ord(c[0]):
				st = False
		elif len(c) > len(v):
			st = False
		n = len(v)
		for (vl, co) in zip(v, c):
			if st == True:
				res += vl
				res += co
			else:
				res += co
				res += vl
		if len(v) > len(c):
			res += v[-1]
		elif len(c) > len(v):
			res += c[-1]
		else:
			pass
		return res


class Solution:

	def rearrange(self, S, N):
		countv = 0
		countc = 0
		dict1 = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
		vowel = ''
		cons = ''
		S = sorted(S)
		for i in range(N):
			if S[i] in dict1:
				countv += 1
				vowel += S[i]
			else:
				countc += 1
				cons += S[i]
		if abs(countv - countc) > 1:
			return -1
		(i, j) = (0, 0)
		string1 = ''
		string2 = ''
		count = 0
		if countv > countc:
			while i < countv and j < countc:
				if count % 2 == 0:
					string1 += vowel[i]
					i += 1
				else:
					string1 += cons[j]
					j += 1
				count += 1
			if i < countv:
				string1 += vowel[i]
		elif countc > countv:
			while i < countv and j < countc:
				if count % 2 != 0:
					string1 += vowel[i]
					i += 1
				else:
					string1 += cons[j]
					j += 1
				count += 1
			if j < countc:
				string1 += cons[j]
		else:
			(i, j) = (0, 0)
			while i < countv and j < countc:
				if count % 2 == 0:
					string1 += vowel[i]
					i += 1
				else:
					string1 += cons[j]
					j += 1
				count += 1
			if i < countv:
				string1 += vowel[i]
			if j < countc:
				string1 += cons[j]
			(i, j) = (0, 0)
			count = 0
			while i < countv and j < countc:
				if count % 2 != 0:
					string2 += vowel[i]
					i += 1
				else:
					string2 += cons[j]
					j += 1
				count += 1
			if i < countv:
				string2 += vowel[i]
			if j < countc:
				string2 += cons[j]
			if string1 < string2:
				return string1
			else:
				return string2
		return string1


class Solution:

	def rearrange(self, S, N):
		t_ = 'bcdfghjklmnpqrstvwxyz'
		p = 'aeiou'
		d = {}
		c = 0
		c_ = 0
		d_ = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
		for i in range(N):
			if S[i] == 'a' or S[i] == 'e' or S[i] == 'i' or (S[i] == 'o') or (S[i] == 'u'):
				d_[S[i]] += 1
				c_ += 1
			else:
				if S[i] not in d.keys():
					d[S[i]] = 1
				else:
					d[S[i]] += 1
				c += 1
		S = ''
		if abs(c - c_) != 1 and abs(c - c_) != 0:
			return -1
		else:
			if c - c_ == 1:
				f = 0
			elif c_ - c == 1:
				f = 1
			else:
				for i in range(5):
					if d_[p[i]] != 0:
						vow = p[i]
						break
				for i in range(21):
					if t_[i] in d.keys():
						con = t_[i]
						break
				if con > vow:
					f = 1
				else:
					f = 0
			i = 0
			c1 = 0
			c2 = 0
			while i < N:
				if f == 0:
					while c1 < 21:
						if t_[c1] in d.keys():
							d[t_[c1]] -= 1
							S += t_[c1]
							if d[t_[c1]] == 0:
								c1 += 1
							break
						else:
							c1 += 1
					f = 1
				else:
					while c2 < 5:
						if d_[p[c2]] != 0:
							d_[p[c2]] -= 1
							S += p[c2]
							if d_[p[c2]] == 0:
								c2 += 1
							break
						else:
							c2 += 1
					f = 0
				i += 1
		return S


class Solution:

	def rearrange(self, S, N):
		i = 0
		j = 0
		k = 0
		l = 0
		v = []
		c = []
		for i in S:
			if i == 'a' or i == 'e' or i == 'i' or (i == 'o') or (i == 'u'):
				v.append(i)
			else:
				c.append(i)
		v.sort()
		c.sort()
		res = ''
		if abs(len(v) - len(c)) <= 1:
			i = 0
			j = 0
			k = 0
			if len(c) == len(v):
				if c[0] > v[0]:
					while i + j < len(c) + len(v):
						if k % 2 == 0:
							res = res + v[i]
							i = i + 1
						else:
							res = res + c[j]
							j = j + 1
						k = k + 1
				else:
					while i + j < len(c) + len(v):
						if k % 2 == 0:
							res = res + c[i]
							i = i + 1
						else:
							res = res + v[j]
							j = j + 1
						k = k + 1
			elif len(v) > len(c):
				while i + j < len(c) + len(v):
					if k % 2 == 0:
						res = res + v[i]
						i = i + 1
					else:
						res = res + c[j]
						j = j + 1
					k = k + 1
			else:
				while i + j < len(c) + len(v):
					if k % 2 == 0:
						res = res + c[i]
						i = i + 1
					else:
						res = res + v[j]
						j = j + 1
					k = k + 1
			return res
		else:
			return '-1'


class Solution:

	def rearrange(self, S, N):
		vowels = set('aeiou')
		arr = []
		brr = []
		for item in S:
			if item in vowels:
				arr.append(item)
			else:
				brr.append(item)
		arr.sort()
		brr.sort()
		if abs(len(arr) - len(brr)) > 1:
			return -1
		output = []
		if len(brr) > len(arr) or (len(brr) == len(arr) and brr[0] > arr[0]):
			output.append(brr.pop())
		while arr and brr:
			output.append(arr.pop())
			output.append(brr.pop())
		output += arr + brr
		return ''.join(reversed(output))


class Solution:

	def rearrange(self, S, N):
		if N == 1:
			return S
		chars = [0] * 26
		for ch in S:
			chars[ord(ch) - 97] += 1
		vowels = sum([chars[0], chars[4], chars[8], chars[14], chars[20]])
		if abs(2 * vowels - sum(chars)) > 1:
			return -1
		vowels_string = ''
		consonent_string = ''
		for i in range(26):
			if i in [0, 4, 8, 14, 20]:
				vowels_string += chr(97 + i) * chars[i]
			else:
				consonent_string += chr(97 + i) * chars[i]
		if vowels_string[0] < consonent_string[0] and len(vowels_string) >= len(consonent_string):
			str1 = vowels_string
			str2 = consonent_string
		else:
			str2 = vowels_string
			str1 = consonent_string
		res = ''
		for i in range(len(str2)):
			res += str1[i] + str2[i]
		if i < len(str1) - 1:
			res += str1[-1]
		return res


class Solution:

	def rearrange(self, S, N):
		st = ''.join(sorted(S, key=str.lower))
		v = 0
		c = 0
		l1 = ''
		l2 = ''
		for i in st:
			if i == 'a' or i == 'e' or i == 'i' or (i == 'o') or (i == 'u'):
				v += 1
				l1 += i
			else:
				c += 1
				l2 += i
		f = 0
		g = 0
		ns = ''
		if v > c + 1 or v < c - 1:
			return -1
		elif v >= c and st[0] == 'a' or st[0] == 'e' or st[0] == 'i' or (st[0] == 'o') or (st[0] == 'u'):
			for i in range(N):
				if i % 2 == 0:
					ns += l1[f]
					f += 1
				else:
					ns += l2[g]
					g += 1
			return ns
		else:
			for i in range(N):
				if i % 2 == 0:
					ns += l2[f]
					f += 1
				else:
					ns += l1[g]
					g += 1
			return ns


class Solution:

	def rearrange(self, S, N):
		S = sorted(S)
		vowels = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
		v = []
		c = []
		for i in S:
			if i in vowels:
				v.append(i)
			else:
				c.append(i)
		if abs(len(v) - len(c)) > 1:
			return -1
		if len(v) < len(c):
			(v, c) = (c, v)
		elif len(v) == len(c):
			if v[0] > c[0]:
				(v, c) = (c, v)
		i = 0
		stg = ''
		while i < len(c):
			stg += v[i]
			stg += c[i]
			i += 1
		if len(v) - len(c) == 1:
			stg += v[i]
		return stg


class Solution:

	def rearrange(self, S, N):
		vowels = [0] * 26
		consonants = [0] * 26
		countVowel = countConsonant = 0
		for char in S:
			if char in 'aeiou':
				vowels[ord(char) - 97] += 1
				countVowel += 1
			else:
				consonants[ord(char) - 97] += 1
				countConsonant += 1
		if abs(countVowel - countConsonant) >= 2:
			return '-1'
		ans = ''
		i = j = 0
		while i < 26 and vowels[i] == 0:
			i += 1
		while j < 26 and consonants[j] == 0:
			j += 1
		while countVowel > 0 and countConsonant > 0:
			vowel = chr(i + 97)
			consonant = chr(j + 97)
			if countVowel == countConsonant:
				if not ans:
					ans += min(vowel, consonant)
					ans += max(vowel, consonant)
				elif ans[-1] in 'aeiou':
					ans += consonant
					ans += vowel
				else:
					ans += vowel
					ans += consonant
			elif countVowel > countConsonant:
				ans += vowel
				ans += consonant
			else:
				ans += consonant
				ans += vowel
			vowels[i] -= 1
			consonants[j] -= 1
			countVowel -= 1
			countConsonant -= 1
			while i < 26 and vowels[i] == 0:
				i += 1
			while j < 26 and consonants[j] == 0:
				j += 1
		if countVowel > 0:
			vowel = chr(i + 97)
			ans += vowel
		if countConsonant > 0:
			consonant = chr(j + 97)
			ans += consonant
		return ans


class Solution:

	def rearrange(self, S, N):
		v = 'aeiou'
		s = sorted(S)
		a = ''
		b = ''
		r = ''
		for i in s:
			if i in v:
				a = a + i
			else:
				b = b + i
		if a == '' or b == '':
			return -1
		n1 = len(a)
		n2 = len(b)
		j = k = 0
		if abs(n1 - n2) == 1 or abs(n1 - n2) == 0:
			if n1 < n2:
				(a, b) = (b, a)
			elif n1 == n2:
				if a[0] > b[0]:
					(a, b) = (b, a)
			for i in range(N):
				if i % 2 == 0 and j < len(a):
					r = r + a[j]
					j = j + 1
				elif k < len(b):
					r = r + b[k]
					k = k + 1
			return r
		else:
			return -1


class Solution:

	def rearrange(self, S, N):
		st = ['a', 'e', 'i', 'o', 'u']
		vow = [0] * 26
		cons = [0] * 26
		numVow = 0
		numCons = 0
		smallestVow = 'u'
		smallestCons = 'z'
		for i in range(N):
			if S[i] < 'a' or S[i] > 'z':
				return -1
			if S[i] not in st:
				cons[ord(S[i]) - ord('a')] += 1
				numCons += 1
				if S[i] < smallestCons:
					smallestCons = S[i]
			else:
				vow[ord(S[i]) - ord('a')] += 1
				numVow += 1
				if S[i] < smallestVow:
					smallestVow = S[i]
		if abs(numVow - numCons) > 1:
			return '-1'
		if numVow == numCons:
			if smallestVow < smallestCons:
				putVow = True
			else:
				putVow = False
		elif numVow > numCons:
			putVow = True
		else:
			putVow = False
		i = 0
		j = 0
		itr = 0
		S = [el for el in S]
		while i < 26 or j < 26:
			if putVow:
				while i < 26 and vow[i] == 0:
					i += 1
				if i == 26:
					break
				S[itr] = chr(ord('a') + i)
				itr += 1
				vow[i] -= 1
				putVow = False
			else:
				while j < 26 and cons[j] == 0:
					j += 1
				if j == 26:
					break
				S[itr] = chr(ord('a') + j)
				itr += 1
				cons[j] -= 1
				putVow = True
		return ''.join(S)


class Solution:

	def rearrange(self, S, N):
		str = ''
		if N == 1:
			return S
		else:
			vo = []
			con = []
			for i in S:
				if i in ['a', 'e', 'i', 'o', 'u']:
					vo.append(i)
				else:
					con.append(i)
			V = len(vo)
			C = len(con)
			vo.sort()
			con.sort()
			if V == 0 or C == 0:
				str = -1
			elif V == C + 1:
				for i in range(N):
					str += vo[i // 2] if i % 2 == 0 else con[i // 2]
			elif C == V + 1:
				for i in range(N):
					str += con[i // 2] if i % 2 == 0 else vo[i // 2]
			elif V == C:
				if vo[0] < con[0]:
					for i in range(N):
						str += vo[i // 2] if i % 2 == 0 else con[i // 2]
				else:
					for i in range(N):
						str += con[i // 2] if i % 2 == 0 else vo[i // 2]
			else:
				str = -1
		return str


class Solution:

	def rearrange(self, S, N):
		s = {'a', 'e', 'i', 'o', 'u'}
		Sa = list(S)
		Sa.sort()
		vc = 0
		cc = 0
		dv = []
		dc = []
		ans = ''
		for i in Sa:
			if i in s:
				vc += 1
				dv.append(i)
			else:
				cc += 1
				dc.append(i)
		if abs(vc - cc) > 1:
			return -1
		p = 0
		if vc == cc:
			if dc[0] > dv[0]:
				while vc > p:
					ans += dv[p] + dc[p]
					p += 1
			else:
				while vc > p:
					ans += dc[p] + dv[p]
					p += 1
			return ans
		elif vc > cc:
			ans += dv[0]
			while cc > p:
				ans += dc[p] + dv[p + 1]
				p += 1
			return ans
		else:
			ans += dc[0]
			while vc > p:
				ans += dv[p] + dc[p + 1]
				p += 1
			return ans


class Solution:

	def rearrange(self, S, N):
		(K, L, res) = ([], [], '')
		for i in S:
			if i in 'aeiou':
				K.append(i)
			else:
				L.append(i)
		(x, y) = (len(K), len(L))
		if abs(x - y) > 1:
			return -1
		K.sort()
		L.sort()
		if x > y:
			for i in range(y):
				res += K[i]
				res += L[i]
			res += K[-1]
		elif y > x:
			for i in range(x):
				res += L[i]
				res += K[i]
			res += L[-1]
		elif K[0] < L[0]:
			for i in range(y):
				res += K[i]
				res += L[i]
		else:
			for i in range(y):
				res += L[i]
				res += K[i]
		return res


class Solution:

	def rearrange(self, S, N):
		f = [i for i in str(S)]
		f.sort()
		vov = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
		v = []
		c = []
		for i in f:
			if i in vov:
				v.append(i)
			else:
				c.append(i)
		temp1 = len(v)
		a = ''
		temp2 = len(c)
		if temp2 < temp1 - 1 or temp1 < temp2 - 1:
			return -1
		h = max(temp1, temp2)
		l = min(temp1, temp2)
		if l == h:
			if v[0] < c[0]:
				for i in range(0, l):
					a += str(v[i])
					a += str(c[i])
			else:
				for i in range(0, l):
					a += str(c[i])
					a += str(v[i])
			return a
		if temp1 == h:
			for i in range(0, l):
				a += str(v[i])
				a += str(c[i])
			if l != h:
				a += str(v[i + 1])
		else:
			for i in range(0, l):
				a += str(c[i])
				a += str(v[i])
			if l != h:
				a += str(c[i + 1])
		return a


class Solution:

	def rearrange(self, S, N):
		(v, c) = ([], [])
		for i in S:
			if i == 'a' or i == 'e' or i == 'i' or (i == 'o') or (i == 'u'):
				v.append(i)
			else:
				c.append(i)
		(v, c) = (sorted(v), sorted(c))
		if len(c) == len(v) + 1 or len(v) == len(c) + 1 or len(c) == len(v):
			s = ''
			if v[0] > c[0]:
				(k1, k2) = (c.copy(), v.copy())
			else:
				(k1, k2) = (v.copy(), c.copy())
			if len(k1) < len(k2):
				(k1, k2) = (k2.copy(), k1.copy())
			(i, j) = (0, 0)
			while i < len(k1) and j < len(k2):
				s += k1[i]
				i += 1
				s += k2[j]
				j += 1
			while i < len(k1):
				s += k1[i]
				i += 1
			while j < len(k2):
				s += k2[j]
				j += 1
			return s
		else:
			return -1


class Solution:

	def rearrange(self, S, N):
		d = []
		e = []
		for i in S:
			if i in 'aeiou':
				d.append(i)
			else:
				e.append(i)
		d.sort()
		e.sort()
		if abs(len(d) - len(e)) > 1:
			return -1
		else:
			f = ''
			if len(d) > len(e):
				for i in range(len(e)):
					f += d[i]
					f += e[i]
				f += d[-1]
			elif len(e) > len(d):
				for i in range(len(d)):
					f += e[i]
					f += d[i]
				f += e[-1]
			elif d[0] < e[0]:
				for i in range(len(e)):
					f += d[i]
					f += e[i]
			else:
				for i in range(len(e)):
					f += e[i]
					f += d[i]
			return f


class Solution:

	def rearrange(self, s, n):
		a = []
		b = []
		l = {'a', 'e', 'i', 'o', 'u'}
		for i in s:
			if i in l:
				a.append(i)
			else:
				b.append(i)
		a.sort()
		b.sort()
		res = ''
		if abs(len(a) - len(b)) > 1:
			return '-1'
		if len(a) == len(b):
			for i in range(min(len(a), len(b))):
				res += a[i] + b[i]
			ans = ''
			for i in range(min(len(a), len(b))):
				ans += b[i] + a[i]
			return min(ans, res)
		elif len(a) > len(b):
			for i in range(min(len(a), len(b))):
				res += a[i] + b[i]
			res = res + a[-1]
			return res
		else:
			for i in range(min(len(a), len(b))):
				res += b[i] + a[i]
			res += b[i]
			return res


class Solution:

	def rearrange(self, S, N):
		vowels = []
		consonants = []
		for char in S:
			if char in 'aeiou':
				vowels.append(char)
			else:
				consonants.append(char)
		vowels.sort()
		consonants.sort()
		ans = ''
		ans1 = ''
		ans2 = ''
		if abs(len(vowels) - len(consonants)) > 1:
			return -1
		elif len(vowels) > len(consonants):
			for i in range(len(consonants)):
				ans += vowels[i] + consonants[i]
			ans += vowels[-1]
		elif len(vowels) < len(consonants):
			for i in range(len(vowels)):
				ans += consonants[i] + vowels[i]
			ans += consonants[-1]
		else:
			for i in range(min(len(vowels), len(consonants))):
				ans1 += vowels[i] + consonants[i]
				ans2 += consonants[i] + vowels[i]
			ans = ans1 if str(ans1) <= str(ans2) else ans2
		return ans


VOWELS = {'a', 'e', 'i', 'o', 'u'}

class Solution:

	def mixin(self, s1, s2, n1, n2):
		n = max(n1, n2)
		res = ''
		for i in range(n):
			res += s1[i]
			if i < n2:
				res += s2[i]
		return res

	def rearrange(self, s, n):
		(vowels, consonants) = ([], [])
		for c in s:
			if c in VOWELS:
				vowels.append(c)
			else:
				consonants.append(c)
		(vn, cn) = (len(vowels), len(consonants))
		if abs(vn - cn) > 1:
			return '-1'
		vowels.sort()
		consonants.sort()
		if vn > cn or (vn == cn and vowels[0] < consonants[0]):
			return self.mixin(vowels, consonants, vn, cn)
		else:
			return self.mixin(consonants, vowels, cn, vn)


class Solution:

	def rearrange(self, S, N):
		newArrCon = [0 for _ in range(26)]
		arrVow = []
		arrCon = []
		for i in S:
			newArrCon[ord(i) - 97] += 1
		for i in range(len(newArrCon)):
			if not chr(97 + i) in ['a', 'e', 'i', 'o', 'u']:
				for k in range(newArrCon[i]):
					arrCon.append(chr(97 + i))
			else:
				for k in range(newArrCon[i]):
					arrVow.append(chr(97 + i))
		if abs(len(arrVow) - len(arrCon)) > 1:
			return -1
		if arrVow[0] < arrCon[0] and len(arrVow) >= len(arrCon):
			str1 = arrVow
			str2 = arrCon
		else:
			str1 = arrCon
			str2 = arrVow
		res = ''
		for i in range(len(str2)):
			res += str1[i] + str2[i]
		if i < len(str1) - 1:
			res += str1[-1]
		return res


from collections import Counter

class Solution:

	def rearrange(self, S, N):
		d = Counter()
		(v, c) = (0, 0)
		for l in S:
			if l in 'aeiou':
				v += 1
			else:
				c += 1
			d[l] += 1
		if abs(v - c) > 1:
			return -1
		vw = True if v > c else False
		res = ''
		vw = True if v > c else False
		vl = [c for c in 'aeiou' if d[c]]
		cl = [chr(i) for i in range(97, 97 + 26) if d[chr(i)] and chr(i) not in 'aeiou']
		if v == c:
			vw = True if vl and cl and (vl[0] < cl[0]) else False
		(v, c) = (0, 0)
		for _ in range(N):
			if vw:
				while not d[vl[v]]:
					v += 1
				res += vl[v]
				d[vl[v]] -= 1
			else:
				while not d[cl[c]]:
					c += 1
				res += cl[c]
				d[cl[c]] -= 1
			vw = not vw
		return res


class Solution:

	def rearrange(self, S, N):
		vows = {}
		cons = {}
		(vlen, clen) = (0, 0)
		for c in S:
			if c == 'a' or c == 'e' or c == 'i' or (c == 'o') or (c == 'u'):
				if c not in vows.keys():
					vows[c] = 0
				vows[c] += 1
				vlen += 1
			else:
				if c not in cons.keys():
					cons[c] = 0
				cons[c] += 1
				clen += 1
		if abs(vlen - clen) > 1:
			return -1
		consonant = 'bcdfghjklmnpqrstvwxyz'
		vowel = 'aeiou'
		final = ''
		(i, j) = (0, 0)
		if vlen > clen:
			while i < 5 and j < 21:
				while i < 5:
					if vowel[i] in vows.keys():
						if vows[vowel[i]] != 0:
							final += vowel[i]
							vows[vowel[i]] -= 1
							break
					i += 1
				while j < 21:
					if consonant[j] in cons.keys():
						if cons[consonant[j]] != 0:
							final += consonant[j]
							cons[consonant[j]] -= 1
							break
					j += 1
		elif clen > vlen:
			while i < 5 and j < 21:
				while j < 21:
					if consonant[j] in cons.keys():
						if cons[consonant[j]] != 0:
							final += consonant[j]
							cons[consonant[j]] -= 1
							break
					j += 1
				while i < 5:
					if vowel[i] in vows.keys():
						if vows[vowel[i]] != 0:
							final += vowel[i]
							vows[vowel[i]] -= 1
							break
					i += 1
		else:
			for ch in 'abcdefghijklmnopqrstuvwxyz':
				if ch in vows.keys():
					while i < 5 and j < 21:
						while i < 5:
							if vowel[i] in vows.keys():
								if vows[vowel[i]] != 0:
									final += vowel[i]
									vows[vowel[i]] -= 1
									break
							i += 1
						while j < 21:
							if consonant[j] in cons.keys():
								if cons[consonant[j]] != 0:
									final += consonant[j]
									cons[consonant[j]] -= 1
									break
							j += 1
					break
				elif ch in cons.keys():
					while i < 5 and j < 21:
						while j < 21:
							if consonant[j] in cons.keys():
								if cons[consonant[j]] != 0:
									final += consonant[j]
									cons[consonant[j]] -= 1
									break
							j += 1
						while i < 5:
							if vowel[i] in vows.keys():
								if vows[vowel[i]] != 0:
									final += vowel[i]
									vows[vowel[i]] -= 1
									break
							i += 1
					break
		return final


def merge(l1, l2):
	i = 0
	j = 0
	ans = ''
	while i < len(l1) and j < len(l2):
		ans += l1[i]
		ans += l2[i]
		i += 1
		j += 1
	if i < len(l1) or j < len(l2):
		ans += l1[-1]
	return ans

def solve(s):
	vowles = 'aeiou'
	vow = []
	con = []
	for i in s:
		if i in vowles:
			vow.append(i)
		else:
			con.append(i)
	vow = list(sorted(vow))
	con = list(sorted(con))
	if abs(len(vow) - len(con)) > 1:
		return -1
	elif len(vow) > len(con):
		return merge(vow, con)
	elif len(con) > len(vow):
		return merge(con, vow)
	elif len(vow) == len(con):
		if vow[0] < con[0]:
			return merge(vow, con)
		else:
			return merge(con, vow)

class Solution:

	def rearrange(self, S, N):
		return solve(S)


class Solution:

	def rearrange(self, S, N):
		arr1 = [0 for i in range(26)]
		arr2 = [0 for i in range(26)]
		count1 = 0
		count2 = 0
		for i in S:
			if i in ('a', 'e', 'i', 'o', 'u'):
				arr1[ord(i) - ord('a')] += 1
				count1 += 1
			else:
				arr2[ord(i) - ord('a')] += 1
				count2 += 1
		s = ''
		flag1 = 1
		if count1 - count2 != 0 and count1 - count2 != 1 and (count1 - count2 != -1):
			return '-1'
		else:
			i = 0
			j = 0
			while i < 26 or j < 26:
				while i < 26 and arr1[i] == 0:
					i += 1
				while j < 26 and arr2[j] == 0:
					j += 1
				if count1 - count2 == 0:
					if i < j and flag1 == 1:
						if i < 26 and arr1[i] != 0:
							s += chr(ord('a') + i)
							arr1[i] -= 1
						if j < 26 and arr2[j] != 0:
							s += chr(ord('a') + j)
							arr2[j] -= 1
						flag1 = 0
					elif i > j and flag1 == 1:
						if j < 26 and arr2[j] != 0:
							s += chr(ord('a') + j)
							arr2[j] -= 1
						if i < 26 and arr1[i] != 0:
							s += chr(ord('a') + i)
							arr1[i] -= 1
						flag1 = 1
					elif flag1 == 0:
						if i < 26 and arr1[i] != 0:
							s += chr(ord('a') + i)
							arr1[i] -= 1
						if j < 26 and arr2[j] != 0:
							s += chr(ord('a') + j)
							arr2[j] -= 1
					elif flag1 == 1:
						if j < 26 and arr2[j] != 0:
							s += chr(ord('a') + j)
							arr2[j] -= 1
						if i < 26 and arr1[i] != 0:
							s += chr(ord('a') + i)
							arr1[i] -= 1
				if count1 - count2 == 1:
					if i < 26 and arr1[i] != 0:
						s += chr(ord('a') + i)
						arr1[i] -= 1
					if j < 26 and arr2[j] != 0:
						s += chr(ord('a') + j)
						arr2[j] -= 1
				if count1 - count2 == -1:
					if j < 26 and arr2[j] != 0:
						s += chr(ord('a') + j)
						arr2[j] -= 1
					if i < 26 and arr1[i] != 0:
						s += chr(ord('a') + i)
						arr1[i] -= 1
				if i < 26 and arr1[i] == 0:
					i += 1
				if j < 26 and arr2[j] == 0:
					j += 1
		return s


class Solution:

	def findFirst(self, arr):
		i = 0
		while i < 26:
			if arr[i] != 0:
				break
			i += 1
		return i

	def rearrange(self, S, N):
		vow = cons = 0
		varr = [0] * 26
		carr = [0] * 26
		vowels = set(['a', 'e', 'i', 'o', 'u'])
		for c in S:
			if c in vowels:
				varr[ord(c) - ord('a')] += 1
				vow += 1
			else:
				carr[ord(c) - ord('a')] += 1
				cons += 1
		if abs(vow - cons) > 1:
			return '-1'
		word = [None] * N

		def makeWord(arr, k):
			for i in range(26):
				while arr[i] > 0:
					word[k] = chr(ord('a') + i)
					k += 2
					arr[i] -= 1
				i += 1
		if vow == cons:
			v = self.findFirst(varr)
			c = self.findFirst(carr)
			if v < c:
				makeWord(varr, 0)
				makeWord(carr, 1)
			if c < v:
				makeWord(carr, 0)
				makeWord(varr, 1)
		elif vow > cons:
			makeWord(varr, 0)
			makeWord(carr, 1)
		else:
			makeWord(carr, 0)
			makeWord(varr, 1)
		return ''.join(word)


class Solution:

	def rearrange(self, S, N):
		vowel = 'aeiou'
		vow = ''
		cons = ''
		S = sorted(S)
		res = ''
		i = 0
		j = 0
		for el in S:
			if el in vowel:
				vow += el
			else:
				cons += el
		if abs(len(vow) - len(cons)) <= 1:
			if len(vow) == len(cons):
				if vow[0] > cons[0]:
					for k in range(N):
						if k % 2 == 1:
							res += vow[i]
							i += 1
						else:
							res += cons[j]
							j += 1
				else:
					for k in range(N):
						if k % 2 == 0:
							res += vow[i]
							i += 1
						else:
							res += cons[j]
							j += 1
			elif len(vow) > len(cons):
				for k in range(N):
					if k % 2 == 0:
						res += vow[i]
						i += 1
					else:
						res += cons[j]
						j += 1
			else:
				for k in range(N):
					if k % 2 == 1:
						res += vow[i]
						i += 1
					else:
						res += cons[j]
						j += 1
			return res
		return -1


class Solution:

	def rearrange(self, S, N):
		vowelArr = []
		consonArr = []
		countV = 0
		ans = ''
		countC = 0
		for i in S:
			if i in ['a', 'e', 'i', 'o', 'u']:
				countV += 1
				vowelArr.append(i)
			else:
				countC += 1
				consonArr.append(i)
		vowelArr.sort()
		consonArr.sort()
		if abs(countC - countV) > 1:
			return -1
		elif countC == countV:
			if ord(vowelArr[0]) < ord(consonArr[0]):
				for i in range(countC):
					ans = ans + vowelArr[i]
					ans = ans + consonArr[i]
			else:
				for i in range(countC):
					ans = ans + consonArr[i]
					ans = ans + vowelArr[i]
		elif countC > countV:
			for i in range(countV):
				ans = ans + consonArr[i]
				ans = ans + vowelArr[i]
			ans = ans + consonArr[-1]
		elif countC < countV:
			for i in range(countC):
				ans = ans + vowelArr[i]
				ans = ans + consonArr[i]
			ans = ans + vowelArr[-1]
		return ans


class Solution:

	def rearrange(self, S, N):
		result = ''
		vowels = [ch for ch in S if self.isVowel(ch)]
		consonants = [ch for ch in S if not self.isVowel(ch)]
		if abs(len(vowels) - len(consonants)) > 1:
			return '-1'
		vowels.sort()
		consonants.sort()
		if len(vowels) > len(consonants):
			for index in range(0, len(consonants)):
				result += vowels[index]
				result += consonants[index]
			result += vowels[-1]
		elif len(consonants) > len(vowels):
			for index in range(0, len(vowels)):
				result += consonants[index]
				result += vowels[index]
			result += consonants[-1]
		elif vowels[0] < consonants[0]:
			for index in range(0, len(vowels)):
				result += vowels[index]
				result += consonants[index]
		else:
			for index in range(0, len(vowels)):
				result += consonants[index]
				result += vowels[index]
		return result

	def isVowel(self, ch):
		kVowels = ['a', 'e', 'i', 'o', 'u']
		return ch in kVowels


class Solution:

	def rearrange(self, S, N):
		vowels = ['a', 'e', 'i', 'o', 'u']
		(arr1, arr2) = ([], [])
		for i in range(N):
			if S[i] in vowels:
				arr1.append(S[i])
			else:
				arr2.append(S[i])
		arr1.sort()
		arr2.sort()
		if abs(len(arr1) - len(arr2)) > 1:
			return '-1'
		(string1, string2) = ('', '')
		x = max(len(arr1), len(arr2))
		y = min(len(arr1), len(arr2))
		for i in range(0, min(len(arr1), len(arr2))):
			string1 += arr1[i] + arr2[i]
			string2 += arr2[i] + arr1[i]
		if x == len(arr1) and x != len(arr2):
			for i in range(y, x):
				string1 += arr1[i]
				string2 += arr1[i]
		if x == len(arr2) and x != len(arr1):
			for i in range(y, x):
				string1 += arr2[i]
				string2 += arr2[i]
		if x == len(arr1):
			return min(string1, string2)
		return string2


class Solution:

	def rearrange(self, S, N):
		v = []
		c = []
		for i in S:
			if i in 'aeiou':
				v.append(i)
			else:
				c.append(i)
		V = len(v)
		C = len(c)
		if abs(C - V) > 1:
			return -1
		v.sort()
		c.sort()
		s = ''
		if V > C:
			for i in range(min(C, V)):
				s += v[i] + c[i]
			return s + v[-1]
		elif C > V:
			for i in range(min(C, V)):
				s += c[i] + v[i]
			return s + c[-1]
		else:
			(c, v) = (min(c, v), max(c, v))
			for i in range(min(C, V)):
				s += c[i] + v[i]
			return s


class Solution:

	def rearrange(self, S, N):
		vow = []
		con = []
		res = ''
		for i in S:
			if i == 'a' or i == 'e' or i == 'i' or (i == 'o') or (i == 'u'):
				vow.append(i)
			else:
				con.append(i)
		vow.sort()
		con.sort()
		l1 = len(vow)
		l2 = len(con)
		k = min(l1, l2)
		if abs(l1 - l2) <= 1:
			if l1 > l2:
				for i in range(k):
					res += vow[i]
					res += con[i]
				res += vow[l1 - 1]
			elif l2 > l1:
				for i in range(k):
					res += con[i]
					res += vow[i]
				res += con[l2 - 1]
			else:
				for i in range(k):
					if ord(vow[0]) < ord(con[0]):
						res += vow[i]
						res += con[i]
					else:
						res += con[i]
						res += vow[i]
		else:
			res += '-1'
		return res


class Solution:

	def rearrange(self, S, N):
		vowels = set(['a', 'e', 'i', 'o', 'u'])
		vowel_list = []
		cons_list = []
		for alpha in S:
			if alpha in vowels:
				vowel_list.append(alpha)
			else:
				cons_list.append(alpha)
		if abs(len(vowel_list) - len(cons_list)) > 1:
			return -1
		vowel_list.sort()
		cons_list.sort()
		ans = []
		if len(vowel_list) > len(cons_list):
			ans = self.make_list(vowel_list, cons_list)
			ans.append(vowel_list[-1])
		elif len(vowel_list) < len(cons_list):
			ans = self.make_list(cons_list, vowel_list)
			ans.append(cons_list[-1])
		elif vowel_list[0] < cons_list[0]:
			ans = self.make_list(vowel_list, cons_list)
		else:
			ans = self.make_list(cons_list, vowel_list)
		return ''.join(ans)

	def make_list(self, l1, l2):
		ans = []
		for (a, b) in zip(l1, l2):
			ans.append(a)
			ans.append(b)
		return ans


class Solution:

	def rearrange(self, S, N):
		temp = 'aeiou'
		vow = []
		nonvow = []
		for i in S:
			if i in temp:
				vow.append(i)
			else:
				nonvow.append(i)
		siVow = len(vow)
		siNonVow = len(nonvow)
		si = siVow - siNonVow
		if si != 0 and si != -1 and (si != 1):
			return -1
		vow.sort()
		nonvow.sort()
		newstr = ''
		l = 0
		if si > 0:
			while l < siVow:
				newstr = newstr + vow[l]
				if l < siVow - 1:
					newstr = newstr + nonvow[l]
				l += 1
			if si == 0:
				newstr = newstr + nonvow[l - 1]
		elif si < 0:
			while l < siNonVow:
				newstr = newstr + nonvow[l]
				if l < siNonVow - 1:
					newstr = newstr + vow[l]
				l += 1
		elif vow[l] < nonvow[l]:
			while l < siVow:
				newstr = newstr + vow[l]
				newstr = newstr + nonvow[l]
				l += 1
		else:
			while l < siVow:
				newstr = newstr + nonvow[l]
				newstr = newstr + vow[l]
				l += 1
		return newstr


class Solution:

	def rearrange(self, S, N):
		a = []
		b = []
		for i in S:
			if i in ['a', 'e', 'i', 'o', 'u']:
				a.append(i)
			else:
				b.append(i)
		a.sort()
		b.sort()
		x = ''
		if abs(len(a) - len(b)) > 1:
			return -1
		elif a[0] < b[0] and len(a) >= len(b):
			for i in range(N):
				try:
					if i % 2 == 0:
						x = x + a[i // 2]
					else:
						x += b[i // 2]
				except:
					pass
			return x
		elif a[0] < b[0] and len(a) < len(b):
			(a, b) = (b, a)
			for i in range(N):
				try:
					if i % 2 == 0:
						x = x + a[i // 2]
					else:
						x += b[i // 2]
				except:
					pass
			return x
		elif a[0] > b[0] and len(a) > len(b):
			for i in range(N):
				try:
					if i % 2 == 0:
						x = x + a[i // 2]
					else:
						x += b[i // 2]
				except:
					pass
			return x
		else:
			(a, b) = (b, a)
			for i in range(N):
				try:
					if i % 2 == 0:
						x = x + a[i // 2]
					else:
						x += b[i // 2]
				except:
					pass
			return x


class Solution:

	def rearrange(self, S, N):
		vowels = []
		cons = []
		for i in S:
			if i in ('a', 'e', 'i', 'o', 'u'):
				vowels.append(i)
			else:
				cons.append(i)
		vowels.sort()
		cons.sort()
		s = ''
		i = 0
		j = 0
		if len(vowels) != len(cons):
			if len(vowels) == len(cons) + 1:
				while i < len(vowels) and j < len(cons):
					s += vowels[i] + cons[j]
					i += 1
					j += 1
				s += vowels[i]
			elif len(vowels) + 1 == len(cons):
				while i < len(cons) and j < len(vowels):
					s += cons[i] + vowels[j]
					i += 1
					j += 1
				s += cons[i]
			else:
				return -1
		elif vowels[0] < cons[0]:
			while i < len(vowels) and j < len(cons):
				s += vowels[i] + cons[j]
				i += 1
				j += 1
		else:
			while i < len(cons) and j < len(vowels):
				s += cons[i] + vowels[j]
				i += 1
				j += 1
		return s


class Solution:

	def rearrange(self, S, N):
		v = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
		vowels = []
		consonants = []
		for i in S:
			if v.get(i, 0) == 1:
				vowels.append(i)
			else:
				consonants.append(i)
		vLength = len(vowels)
		cLength = len(consonants)
		if vLength == cLength or vLength - 1 == cLength:
			vowels.sort()
			consonants.sort()
			ans = []
			i = 1
			j = 1
			ans.append(vowels[0])
			ans.append(consonants[0])
			ans.sort()
			flag = -1
			if v.get(ans[1], 0) == 1:
				flag = 1
			while i < vLength and j < cLength:
				if flag == -1:
					ans.append(vowels[i])
					i += 1
				else:
					ans.append(consonants[j])
					j += 1
				if len(ans) == N:
					break
				flag *= -1
			if i == vLength and j == cLength:
				return ''.join(ans)
			elif i == vLength:
				ans.append(consonants[j])
				return ''.join(ans)
			else:
				ans.append(vowels[i])
				return ''.join(ans)
		elif vLength + 1 == cLength:
			vowels.sort()
			consonants.sort()
			ans = []
			i = 1
			j = 1
			ans.append(consonants[0])
			ans.append(vowels[0])
			flag = 1
			while i < vLength and j < cLength:
				if flag == -1:
					ans.append(vowels[i])
					i += 1
				else:
					ans.append(consonants[j])
					j += 1
				if len(ans) == N:
					break
				flag *= -1
			if i == vLength and j == cLength:
				return ''.join(ans)
			elif i == vLength:
				ans.append(consonants[j])
				return ''.join(ans)
			else:
				ans.append(vowels[i])
				return ''.join(ans)
		return -1


class Solution:

	def rearrange(self, S, N):
		s = set('aeiou')
		v = []
		c = []
		for i in S:
			if i in s:
				v.append(i)
			else:
				c.append(i)
		v.sort()
		c.sort()
		if abs(len(v) - len(c)) > 1:
			return -1
		if len(v) < len(c):
			isVowel = False
		elif len(v) > len(c):
			isVowel = True
		elif v[0] < c[0]:
			isVowel = True
		else:
			isVowel = False
		i = 0
		j = 0
		ans = ''
		while i < len(v) or j < len(c):
			if isVowel:
				ans += v[i]
				i += 1
				isVowel = False
			else:
				ans += c[j]
				j += 1
				isVowel = True
		return ans


class Solution:

	def rearrange(self, S, N):
		vowels = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
		temp = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
		res1 = ''
		res2 = ''
		res3 = ''
		for char in S:
			if char in 'aeiou':
				if char not in vowels:
					vowels[char] = 1
				else:
					vowels[char] += 1
			else:
				temp[char] += 1
		for i in range(97, 123):
			if temp[chr(i)] != 0:
				for j in range(temp[chr(i)]):
					res1 += chr(i)
			if chr(i) in vowels and vowels[chr(i)] != 0:
				for k in range(vowels[chr(i)]):
					res2 += chr(i)
		(r1, r2) = (len(res1), len(res2))
		if abs(r2 - r1) != 1 and abs(r2 - r1) != 0:
			return -1
		(i, j) = (0, 0)
		if r1 == 0 or r2 == 0:
			return res1 + res2
		if abs(r2 - r1) == 1:
			if r1 > r2:
				flag = 0
			else:
				flag = 1
		elif ord(res1[0]) > ord(res2[0]):
			flag = 1
		else:
			flag = 0
		while i < r1 and j < r2:
			if flag == 1:
				res3 += res2[j] + res1[i]
			else:
				res3 += res1[i] + res2[j]
			i += 1
			j += 1
		if j < r2:
			res3 += res2[j]
		if i < r1:
			res3 += res1[i]
		return res3


class Solution:

	def rearrange(self, S, N):
		(v, c) = ([0] * 26, [0] * 26)
		ans = ''
		(nv, nc) = (0, 0)
		vowels = ['a', 'e', 'i', 'o', 'u']
		for i in S:
			if i in vowels:
				v[ord(i) - ord('a')] += 1
				nv += 1
			else:
				c[ord(i) - ord('a')] += 1
				nc += 1
		if abs(nv - nc) > 1:
			return '-1'
		if nv > nc:
			flag = 0
		elif nc > nv:
			flag = 1
		else:
			for i in range(26):
				if v[i] > 0:
					break
			for j in range(26):
				if c[j] > 0:
					break
			if i > j:
				flag = 1
			else:
				flag = 0
		(i, j) = (0, 0)
		while True:
			if i == 26 or j == 26:
				break
			if flag == 0:
				while i < 26 and v[i] == 0:
					i += 1
				if i < 26:
					ans += chr(i + ord('a'))
					v[i] -= 1
				flag = 1
			else:
				while j < 26 and c[j] == 0:
					j += 1
				if j < 26:
					ans += chr(j + ord('a'))
					c[j] -= 1
				flag = 0
		return ans


class Solution:

	def rearrange(self, S, N):
		VOWEL = ['a', 'e', 'i', 'o', 'u']
		v = [c for c in S if c in VOWEL]
		v.sort()
		c = [c for c in S if c not in VOWEL]
		c.sort()
		if abs(len(c) - len(v)) > 1:
			return -1
		if len(c) == len(v) and c[0] < v[0]:
			(c, v) = (v, c)
		elif len(c) > len(v):
			(c, v) = (v, c)
		z = ''
		for i in range(len(v)):
			z = z + v[i]
			if i < len(c):
				z = z + c[i]
		return z


class Solution:

	def rearrange(self, S, N):
		S = ''.join(sorted(S))
		vowels = []
		consonents = []
		for char in S:
			if char in 'aeiou':
				vowels.append(char)
			else:
				consonents.append(char)
		vowels_length = len(vowels)
		consonents_length = len(consonents)
		if abs(vowels_length - consonents_length) > 1:
			return -1
		result = []
		pointer1 = 0
		pointer2 = 0
		append_vow = True
		if vowels_length == consonents_length:
			if consonents[0] < vowels[0]:
				append_vow = False
		elif vowels_length > consonents_length:
			append_vow = True
		else:
			append_vow = False
		while len(result) != N and pointer1 < vowels_length and (pointer2 < consonents_length):
			if append_vow:
				result.append(vowels[pointer1])
				pointer1 += 1
				append_vow = False
			else:
				result.append(consonents[pointer2])
				pointer2 += 1
				append_vow = True
		if pointer1 != vowels_length:
			result.append(vowels[pointer1])
		if pointer2 != consonents_length:
			result.append(consonents[pointer2])
		return ''.join(result)


import re

class Solution:

	def rearrange(self, S, N):
		vow = re.compile('[aeiou]')
		con = re.compile('[^aeiou]')
		a = vow.findall('%s' % S)
		a.sort()
		b = con.findall('%s' % S)
		b.sort()
		if len(a) - len(b) > 1 or len(b) - len(a) > 1:
			return -1
		list3 = []
		for i in range(len(a) + len(b)):
			try:
				if len(a) > len(b):
					list3.append(a[i])
					list3.append(b[i])
				elif len(b) > len(a):
					list3.append(b[i])
					list3.append(a[i])
				elif a[0] < b[0]:
					list3.append(a[i])
					list3.append(b[i])
				elif a[0] > b[0]:
					list3.append(b[i])
					list3.append(a[i])
			except IndexError:
				break
		return ''.join(list3)


def func(n, vstart, cstart, lv, lc, vwel, cst):
	ans = ''
	if 1:
		for i in range(n):
			if i % 2 == 0:
				if vstart < lv:
					ans += vwel[vstart]
					vstart += 1
				else:
					return -1
			elif cstart < lc:
				ans += cst[cstart]
				cstart += 1
			else:
				return -1
		return ans

def func2(n, vstart, cstart, lv, lc, vwel, cst):
	if 1:
		res = ''
		for i in range(n):
			if i % 2:
				if vstart < lv:
					res += vwel[vstart]
					vstart += 1
				else:
					return -1
			elif cstart < lc:
				res += cst[cstart]
				cstart += 1
			else:
				return -1
		return res

class Solution:

	def rearrange(self, s, n):
		vowel = {}
		conso = {}
		v = 'aeiou'
		for i in range(n):
			if s[i] in v:
				if s[i] in vowel:
					vowel[s[i]] += 1
				else:
					vowel[s[i]] = 1
			elif s[i] in conso:
				conso[s[i]] += 1
			else:
				conso[s[i]] = 1
		sv = sorted(vowel.items())
		sc = sorted(conso.items())
		vwel = ''
		cst = ''
		for i in sv:
			for _ in range(i[1]):
				vwel += i[0]
		for i in sc:
			for _ in range(i[1]):
				cst += i[0]
		ans = ''
		lv = len(vwel)
		lc = len(cst)
		(vstart, cstart) = (0, 0)
		ans = func(n, vstart, cstart, lv, lc, vwel, cst)
		(vstart, cstart) = (0, 0)
		res = func2(n, vstart, cstart, lv, lc, vwel, cst)
		if ans == -1 and res == -1:
			return -1
		if ans == -1 or res == -1:
			if ans == -1:
				return res
			return ans
		if ans < res:
			return ans
		return res


class Solution:

	def rearrange(self, S, N):
		v = ''
		c = ''
		res = ''
		V = ['a', 'e', 'i', 'o', 'u']
		if S.isalpha():
			for i in S:
				if i in V:
					v += i
				else:
					c += i
		if abs(len(v) - len(c)) <= 1:
			v = sorted(v)
			c = sorted(c)
			i = 0
			j = 0
			while i < len(v) or j < len(c):
				if len(v) < len(c):
					if j < len(c):
						res += c[j]
						j += 1
					if i < len(v):
						res += v[i]
						i += 1
				elif len(v) > len(c):
					if i < len(v):
						res += v[i]
						i += 1
					if j < len(c):
						res += c[j]
						j += 1
				elif v[0] < c[0]:
					if i < len(v):
						res += v[i]
						i += 1
					if j < len(c):
						res += c[j]
						j += 1
				else:
					if j < len(c):
						res += c[j]
						j += 1
					if i < len(v):
						res += v[i]
						i += 1
			return res
		else:
			return -1


class Solution:

	def rearrange(self, S, N):
		a = {}
		b = {}
		c = ['a', 'e', 'i', 'o', 'u']
		for i in range(0, len(S)):
			if S[i] in c:
				if S[i] not in b:
					b[S[i]] = 0
				b[S[i]] += 1
			else:
				if S[i] not in a:
					a[S[i]] = 0
				a[S[i]] += 1
		final_string = ''
		vowels = []
		total_vowels = 0
		total_consonant = 0
		for (key, value) in b.items():
			vowels.append([key, value])
			total_vowels += value
		consonant = []
		for (key, value) in a.items():
			consonant.append([key, value])
			total_consonant += value
		if total_vowels != total_consonant and total_vowels != total_consonant + 1 and (total_consonant != total_vowels + 1):
			return -1
		vowels.sort()
		consonant.sort()
		count = 0
		count1 = 0
		if vowels[count][0] < consonant[count1][0] and total_vowels >= total_consonant:
			for i in range(0, len(S), 2):
				if count < len(vowels):
					final_string += vowels[count][0]
					vowels[count][1] -= 1
					if vowels[count][1] == 0:
						count += 1
				if count1 < len(consonant):
					final_string += consonant[count1][0]
					consonant[count1][1] -= 1
					if consonant[count1][1] == 0:
						count1 += 1
			if count < len(vowels):
				if vowels[count][1] > 0:
					final_string += vowels[count][0]
		else:
			for i in range(0, len(S), 2):
				if count < len(consonant):
					final_string += consonant[count][0]
					consonant[count][1] -= 1
					if consonant[count][1] == 0:
						count += 1
				if count1 < len(vowels):
					final_string += vowels[count1][0]
					vowels[count1][1] -= 1
					if vowels[count1][1] == 0:
						count1 += 1
			if count < len(consonant):
				if consonant[count][1] > 0:
					final_string += consonant[count][0]
		return final_string