If we alternate the vowels and consonants in the string `"have"`, we get the following list, arranged alphabetically:
`['ahev', 'aveh', 'ehav', 'evah', 'vahe', 'veha']`. These are the only possibilities in which vowels and consonants are alternated. The first element, `ahev`, is alphabetically lowest. 

Given a string:
* alternate the vowels and consonants and return the lexicographically lowest element in the list
* If any two or more vowels or consonants must follow each other, return `"failed"`
* if the number of vowels and consonants are equal, the first letter of the result must be a vowel.

Examples: 

```Haskell
solve("codewars") = "failed". However you alternate vowels and consonants, two consonants must follow each other
solve("oruder") = "edorur"
solve("orudere") = "ederoru". This is the only option that allows you to alternate vowels & consonants.
```

```if c:
In C, return an allocated string even if the response is "failed".
```

Vowels will be any of "aeiou". Input will be a lowercase string, no spaces. See test cases for more examples. 

Good luck!

If you like this Kata, please try: 

[Consonant value](https://www.codewars.com/kata/59c633e7dcc4053512000073)

[Alternate capitalization](https://www.codewars.com/kata/59cfc000aeb2844d16000075)

Source: codewars | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: def solve(s):
	

Solutions:
def solve(s):
	vowels = sorted((c for c in s if c in 'aeiou'))
	consonants = sorted((c for c in s if c not in 'aeiou'))
	(part1, part2) = sorted((vowels, consonants), key=len, reverse=True)
	part2.append('')
	if len(part1) > len(part2):
		return 'failed'
	return ''.join((a + b for (a, b) in zip(part1, part2)))


import re
VOWELS = re.compile('[aeiuo]')

def solve(s):
	(vows, cons) = (sorted(VOWELS.findall(s)), sorted(VOWELS.sub('', s)))
	(long, short) = sorted((vows, cons), key=len, reverse=True)
	return 'failed' if len(long) - len(short) not in [0, 1] else ''.join((a + b for (a, b) in zip(long, short + [''])))


from itertools import zip_longest

def solve(s):
	vow = sorted((c for c in list(s) if c in 'aeiou'))
	con = sorted((c for c in list(s) if c not in 'aeiou'))
	if abs(len(vow) - len(con)) > 1:
		return 'failed'
	arr = [vow, con] if len(vow) >= len(con) else [con, vow]
	return ''.join((''.join(p) for p in list(zip_longest(*arr, fillvalue=''))))


def solve(s):
	(vow, con) = ([], [])
	for c in s:
		if c in 'aeiou':
			vow.append(c)
		else:
			con.append(c)
	(len_v, len_c) = (len(vow), len(con))
	if len_v - len_c in [0, 1]:
		return ''.join((v + c for (v, c) in zip(sorted(vow), sorted(con) + [''])))
	elif len_v - len_c == -1:
		return ''.join((v + c for (v, c) in zip(sorted(con), sorted(vow) + [''])))
	return 'failed'


def solve(stg):
	split = [[], []]
	for c in sorted(stg):
		split[0 if c in 'aeiou' else 1].append(c)
	(a, b) = sorted(split, key=len, reverse=True)
	if len(a) - len(b) > 1:
		return 'failed'
	return ''.join((f'{c}{d}' for (c, d) in zip(a, b + [''])))


import re

def solve(s):
	vowels = sorted(re.findall('[aeiou]', s))[::-1]
	consonant = sorted(re.findall('[^aeiou]', s))[::-1]
	if abs(len(consonant) - len(vowels)) > 1:
		return 'failed'
	out = []
	if len(vowels) >= len(consonant):
		while vowels and consonant:
			out.append(vowels.pop())
			out.append(consonant.pop())
	else:
		while vowels and consonant:
			out.append(consonant.pop())
			out.append(vowels.pop())
	return consonant and ''.join(out + consonant) or ''.join(out + vowels)


from itertools import zip_longest, chain
vowels = {'a', 'e', 'i', 'o', 'u'}

def solve(s):
	(vow, con) = ([], [])
	for c in s:
		(con, vow)[c in vowels].append(c)
	if abs(len(con) - len(vow)) > 1:
		return 'failed'
	vow.sort()
	con.sort()
	(x, y) = (vow, con) if len(vow) >= len(con) else (con, vow)
	return ''.join(chain.from_iterable(zip_longest(x, y, fillvalue='')))


def solve(s):
	vowels = ''.join(sorted((ch for ch in s if ch in 'aeiou'))) + '_'
	consonants = ''.join(sorted((ch for ch in s if ch not in 'aeiou'))) + '_'
	if abs(len(vowels) - len(consonants)) > 1:
		return 'failed'
	if len(vowels) >= len(consonants):
		res = ''.join((v + c for (v, c) in zip(vowels, consonants)))
	else:
		res = ''.join((v + c for (v, c) in zip(consonants, vowels)))
	return res.strip('_')


from itertools import zip_longest

def solve(s):
	(a, b) = (sorted((x for x in s if x in 'aiueo')), sorted((x for x in s if x not in 'aiueo')))
	if len(b) > len(a):
		(a, b) = (b, a)
	return 'failed' if len(a) - len(b) > 1 else ''.join((f'{x}{y}' for (x, y) in zip_longest(a, b, fillvalue='')))


from itertools import zip_longest

def solve(s):
	v = sorted((x for x in s if x in 'aeiou'))
	c = sorted((x for x in s if x not in 'aeiou'))
	if abs(len(v) - len(c)) > 1:
		return 'failed'
	if len(c) > len(v):
		(v, c) = (c, v)
	return ''.join((a + b for (a, b) in zip_longest(v, c, fillvalue='')))


import re

def solve(s):
	(c, v) = (sorted(re.findall('[^aeiou]', s)), sorted(re.findall('[aeiou]', s)))
	(m, n) = (max(c, v, key=len), min(c, v, key=len)) if len(v) != len(c) else (v, c)
	return ''.join(sum(zip(m, n + ['']), ())) if abs(len(v) - len(c)) <= 1 else 'failed'


def solve(stg):
	split = [[], []]
	for c in sorted(stg):
		split[0 if c in 'aeiou' else 1].append(c)
	(a, b) = sorted(split, key=len, reverse=True)
	if len(a) - len(b) > 1:
		return 'failed'
	result = [''] * len(stg)
	(result[::2], result[1::2]) = (a, b)
	return ''.join(result)


def solve(s):
	(c, v, r) = ([], [], [])
	for m in s:
		if m in 'aeiou':
			v.append(m)
		else:
			c.append(m)
	c.sort()
	v.sort()
	(cl, vl) = (len(c), len(v))
	if abs(cl - vl) > 1:
		return 'failed'
	for i in range(max(cl, vl)):
		if vl >= cl:
			if i < vl:
				r.append(v[i])
			if i < cl:
				r.append(c[i])
		else:
			if i < cl:
				r.append(c[i])
			if i < vl:
				r.append(v[i])
	return ''.join(r)


def solve(s):
	count1 = [sum((1 for i in s if i in 'aeiou')), ''.join(sorted((i for i in s if i in 'aeiou')))]
	count2 = [sum((1 for i in s if i not in 'aeiou')), ''.join(sorted((i for i in s if i not in 'aeiou')))]
	if abs(count1[0] - count2[0]) >= 2:
		return 'failed'
	if len(count1[1]) == len(count2[1]):
		return ''.join((i + j for (i, j) in zip(count1[1], count2[1])))
	elif len(count1[1]) > len(count2[1]):
		return ''.join((i + j for (i, j) in zip(count1[1], count2[1]))) + count1[1][-1]
	else:
		return ''.join((i + j for (i, j) in zip(count2[1], count1[1]))) + count2[1][-1]


from itertools import chain, zip_longest

def solve(s):
	ls_vow = sorted([x for x in s if x in 'aeiou'])
	ls_con = sorted([x for x in s if x not in 'aeiou'])
	if abs(len(ls_vow) - len(ls_con)) > 1:
		return 'failed'
	arr = [ls_vow, ls_con] if len(ls_vow) >= len(ls_con) else [ls_con, ls_vow]
	return ''.join(list(chain(*list(zip_longest(*arr, fillvalue='')))))


from itertools import zip_longest

def solve(s):
	print(s)
	a = list(map(s.lower().count, 'aeiou'))
	print('lv', sum(a))
	l = len(s)
	lv = sum(a)
	lc = l - lv
	print('l', l, 'lc', lc)
	(vw, cn) = ([], [])
	if abs(lv - lc) > 1:
		return 'failed'
	elif lv < lc:
		for x in s:
			if x in 'aeiou':
				vw.append(x)
			else:
				cn.append(x)
		cn = sorted(cn)
		vw = sorted(vw)
		b = list(zip_longest(cn, vw))
	elif lc <= lv:
		for x in s:
			if x in 'aeiou':
				vw.append(x)
			else:
				cn.append(x)
		cn = sorted(cn)
		vw = sorted(vw)
		b = list(zip_longest(vw, cn))
	print(vw)
	print(cn)
	lst = []
	for x in b:
		lst.append(x[0])
		lst.append(x[1])
	print(lst)
	if lst[-1] == None:
		del lst[-1]
	print(lst)
	return ''.join(lst)


def solve(s):
	vowels = 'aeiou'
	s_vowels = sorted((c for c in s if c in vowels))
	s_consonants = sorted((c for c in s if c not in vowels))
	diff = len(s_vowels) - len(s_consonants)
	if diff == -1:
		out_string = s_consonants.pop(0)
		for (v, c) in zip(s_vowels, s_consonants):
			out_string += v + c
	elif diff == 0:
		out_string = ''
		for (v, c) in zip(s_vowels, s_consonants):
			out_string += v + c
	elif diff == 1:
		out_string = s_vowels.pop(0)
		for (c, v) in zip(s_consonants, s_vowels):
			out_string += c + v
	else:
		return 'failed'
	return out_string


def solve(s):
	vowels = sorted([x for x in s if x in 'aeiou'])
	consonants = sorted([x for x in s if x not in vowels])
	difference = len(vowels) - len(consonants)
	s = ''
	if abs(difference) >= 2:
		return 'failed'
	elif abs(difference) == 1:
		if difference == 1:
			s += vowels.pop(0)
		else:
			s += consonants.pop(0)
	if s == '' or s[0] not in 'aeiou':
		s += ''.join((''.join(pair) for pair in zip(vowels, consonants)))
	else:
		s += ''.join((''.join(pair) for pair in zip(consonants, vowels)))
	return s


from itertools import zip_longest

def solve(s):
	(vowels, consonants) = ([], [])
	for c in s:
		if c in 'aeiou':
			vowels.append(c)
		else:
			consonants.append(c)
	if abs(len(vowels) - len(consonants)) > 1:
		return 'failed'
	r = ''
	a = [sorted(vowels), sorted(consonants)]
	if len(vowels) < len(consonants):
		a = a[::-1]
	for (c1, c2) in zip_longest(*a, fillvalue=''):
		r += c1 + c2
	return r


def solve(s):
	vowels = sorted([ch for ch in s if ch in 'aeiou'])
	consonants = sorted([ch for ch in s if ch not in 'aeiou'])
	if abs(len(vowels) - len(consonants)) > 1:
		return 'failed'
	ret = ''
	if len(vowels) == len(consonants):
		for (v, c) in zip(vowels, consonants):
			ret += f'{v}{c}'
	else:
		if len(consonants) > len(vowels):
			zipped = zip(consonants, vowels)
			last = consonants[-1]
		else:
			zipped = zip(vowels, consonants)
			last = vowels[-1]
		for (c, v) in zipped:
			ret += f'{c}{v}'
		ret += last
	return ret