Given a string composed of both lowercase and uppercase letters. Sort it in such a manner such that the uppercase and lowercase letter comes in an alternate manner but in sorted way.
Example 1:
Input:
S = bAwutndekWEdkd
Output: AbEdWddekkntuw
Explanation: letters A,E,W are sorted 
as well as letters b,d,d,d,e,k,k,n,t,u,w are 
sorted and both appears alternately in the 
string as far as possible.
Ã¢â¬â¹Example 2:
Input: 
S = AiBFR
Output: AiBFR
Explanation: letters A,B,F,R and sorted 
as well as letter i. 
User Task:
You don't need to read input or print anything. You just have to complete the function stringSort () which takes a string as input and returns the sorted string as described in the problem description.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1). 
Constraints:
1<=|S|<=1000

Difficulty: EASY
Tags: String algorithms

Sorting

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3

class Solution:
    def stringSort (self,s):
        # your code here

Solutions:
class Solution:

	def stringSort(self, s):
		upper = ''
		lower = ''
		res = ''
		for i in s:
			if i.isupper():
				upper += i
			else:
				lower += i
		upper = sorted(upper)
		lower = sorted(lower)
		if len(upper) < len(lower):
			for j in range(len(upper)):
				res += upper[j] + lower[j]
			for j in range(len(upper), len(lower)):
				res += lower[j]
		elif len(lower) < len(upper):
			for k in range(len(lower)):
				res += upper[k] + lower[k]
			for k in range(len(lower), len(upper)):
				res += upper[k]
		elif len(lower) == len(upper):
			for i in range(len(lower)):
				res += upper[i] + lower[i]
		return res


class Solution:

	def stringSort(self, s):
		a = []
		b = []
		for i in s:
			if i.islower():
				a.append(i)
			else:
				b.append(i)
		a.sort()
		b.sort()
		ans = ''
		i = 0
		j = 0
		while i < len(a) and j < len(b):
			ans += b[j]
			ans += a[i]
			i += 1
			j += 1
		while j < len(b):
			ans += b[j]
			j += 1
		while i < len(a):
			ans += a[i]
			i += 1
		return ans


class Solution:

	def stringSort(self, Str):
		if len(Str) == 1:
			return Str
		else:
			final_Str = ''
			upper_List = []
			lower_List = []
			zero = 0
			for i in Str:
				if i == i.lower():
					lower_List.append(i)
				else:
					upper_List.append(i)
			lower_List.sort()
			upper_List.sort()
			for i in upper_List:
				final_Str += i
				Indxe = zero
				if Indxe < len(lower_List):
					final_Str += lower_List[Indxe]
				zero += 1
			final_Str += ''.join(lower_List[Indxe + 1:])
			return final_Str


class Solution:

	def stringSort(self, s):
		uppercase = ''
		lowercase = ''
		for i in s:
			if i.isupper():
				uppercase += i
			else:
				lowercase += i
		uppercase = sorted(uppercase)
		lowercase = sorted(lowercase)
		res = ''
		ucounter = 0
		lcounter = 0
		for i in range(len(s)):
			if i % 2 == 0:
				if ucounter <= len(uppercase) - 1:
					res += uppercase[ucounter]
					ucounter += 1
				else:
					res += lowercase[lcounter]
					lcounter += 1
			elif lcounter <= len(lowercase) - 1:
				res += lowercase[lcounter]
				lcounter += 1
			else:
				res += uppercase[ucounter]
				ucounter += 1
		return res


class Solution:

	def stringSort(self, s):
		d = {}
		for y in s:
			if y in d:
				d[y] += 1
			else:
				d[y] = 1
		u = ''
		l = ''
		for i in s:
			if i.isupper():
				u += i
			else:
				l += i
		u = sorted(u)
		l = sorted(l)
		y = ''
		m1 = len(l)
		m2 = len(u)
		for i in range(min(m1, m2)):
			y += u[i]
			y += l[i]
		if m1 > m2:
			for i in range(m2, m1):
				y += l[i]
		else:
			for i in range(m1, m2):
				y += u[i]
		return y


class Solution:

	def stringSort(self, s):
		lis = []
		res = []
		ans = ''
		for i in s:
			if i.isupper():
				lis.append(i)
			else:
				res.append(i)
		lis.sort()
		res.sort()
		i = 0
		while len(ans) != len(s):
			if len(lis) > i:
				ans += lis[i]
			if len(res) > i:
				ans += res[i]
			i += 1
		return ans


class Solution:

	def stringSort(self, s):
		cap = []
		small = []
		ans = []
		for v in s:
			if v.upper() == v:
				cap.append(v)
			else:
				small.append(v)
		small.sort()
		cap.sort()
		m = min(len(cap), len(small))
		for i in range(m):
			ans.append(cap[i])
			cap[i] = ''
			ans.append(small[i])
			small[i] = ''
		ans = ans + cap + small
		return ''.join(ans)


class Solution:

	def stringSort(self, s):
		MAX = 26
		n = len(s)
		lCount = [0 for i in range(MAX)]
		uCount = [0 for i in range(MAX)]
		s = list(s)
		for i in range(n):
			if s[i].isupper():
				uCount[ord(s[i]) - ord('A')] += 1
			else:
				lCount[ord(s[i]) - ord('a')] += 1
		i = 0
		j = 0
		k = 0
		while k < n:
			while i < MAX and uCount[i] == 0:
				i += 1
			if i < MAX:
				s[k] = chr(ord('A') + i)
				k += 1
				uCount[i] -= 1
			while j < MAX and lCount[j] == 0:
				j += 1
			if j < MAX:
				s[k] = chr(ord('a') + j)
				k += 1
				lCount[j] -= 1
		return ''.join(s)


class Solution:

	def stringSort(self, s):
		upper = []
		lower = []
		for char in s:
			if char.isupper():
				upper.append(char)
			else:
				lower.append(char)
		upper.sort(reverse=True)
		lower.sort(reverse=True)
		output = ''
		while upper and lower:
			output += upper.pop()
			output += lower.pop()
		output += ''.join(reversed(upper))
		output += ''.join(reversed(lower))
		return output


class Solution:

	def stringSort(self, s):
		upper = []
		lower = []
		for i in range(len(s)):
			if ord(s[i]) >= 65 and ord(s[i]) <= 90:
				upper.append(s[i])
			else:
				lower.append(s[i])
		upper.sort()
		lower.sort()
		out = ''
		i = 0
		j = 0
		while i < len(upper) and j < len(lower):
			out += upper[i] + lower[j]
			i += 1
			j += 1
		while i < len(upper):
			out += upper[i]
			i += 1
		while j < len(lower):
			out += lower[j]
			j += 1
		return out


class Solution:

	def stringSort(self, s):
		cap = [0] * 26
		small = [0] * 26
		for i in s:
			if i.isupper():
				cap[ord(i) - ord('A')] += 1
			else:
				small[ord(i) - ord('a')] += 1
		sample = ''
		i = 0
		j = 0
		while i < len(cap) or j < len(small):
			while i < len(cap) and cap[i] == 0:
				i += 1
			while j < len(small) and small[j] == 0:
				j += 1
			if i != len(cap):
				sample += chr(i + ord('A'))
				cap[i] -= 1
			if j != len(small):
				sample += chr(j + ord('a'))
				small[j] -= 1
		return sample


class Solution:

	def stringSort(self, s):
		st1 = ''
		st2 = ''
		for i in range(len(s)):
			if s[i].isupper():
				st1 += s[i]
		string1 = ''.join(sorted(st1))
		for i in range(len(s)):
			if s[i].islower():
				st2 += s[i]
		string2 = ''.join(sorted(st2))
		s1 = ''
		(i, j) = (0, 0)
		min1 = min(len(string1), len(string2))
		if min1 == len(string1):
			while i < min1:
				s1 += string1[i]
				s1 += string2[j]
				i += 1
				j += 1
			if j <= len(string2) - 1:
				s1 += string2[j:]
		else:
			while j < min1:
				s1 += string1[i]
				s1 += string2[j]
				i += 1
				j += 1
			if i <= len(string1) - 1:
				s1 += string1[i:]
		return s1


class Solution:

	def stringSort(self, s):
		u = ''
		l = ''
		for i in s:
			if i.isupper():
				u = u + i
			else:
				l = l + i
		u = list(u)
		u.sort()
		c = ''.join(u)
		l = list(l)
		l.sort()
		d = ''.join(l)
		l = min(len(c), len(d))
		tx = ''
		i = 0
		while i < l:
			tx = tx + c[i]
			tx = tx + d[i]
			i += 1
		p = max(len(c), len(d))
		for j in range(i, p):
			if p == len(c):
				tx = tx + c[j]
			else:
				tx = tx + d[j]
		return tx


class Solution:

	def stringSort(self, s):
		l = ''
		u = ''
		for i in s:
			if i.isupper():
				u += i
			else:
				l += i
		l = sorted(l)
		u = sorted(u)
		r = ''.join(list(map(lambda x, y: x + y, u, l)))
		n = len(r) // 2
		r = r + ''.join(u[n:])
		r = r + ''.join(l[n:])
		return r


class Solution:

	def stringSort(self, s):
		up = [0 for i in range(26)]
		lo = [0 for i in range(26)]
		for i in s:
			if i >= 'a' and i <= 'z':
				lo[ord(i) - ord('a')] += 1
			else:
				up[ord(i) - ord('A')] += 1
		res = ''
		i = 0
		j = 0
		while i < 26 or j < 26:
			while i < 26 and up[i] == 0:
				i += 1
			if i < 26:
				res += chr(ord('A') + i)
				up[i] -= 1
			while j < 26 and lo[j] == 0:
				j += 1
			if j < 26:
				res += chr(ord('a') + j)
				lo[j] -= 1
		return res


class Solution:

	def stringSort(self, s):
		upper = []
		lower = []
		for i in s:
			if i.islower():
				lower.append(i)
			else:
				upper.append(i)
		upper.sort()
		lower.sort()
		(n, m) = (len(upper), len(lower))
		(j, k) = (0, 0)
		i = 0
		res = [None] * (n + m)
		while j < n and k < m:
			if i % 2 == 0:
				res[i] = upper[j]
				j += 1
			else:
				res[i] = lower[k]
				k += 1
			i += 1
		while j < n:
			res[i] = upper[j]
			j += 1
			i += 1
		while k < m:
			res[i] = lower[k]
			k += 1
			i += 1
		return ''.join(res)


class Solution:

	def stringSort(self, s):
		u = ''
		l = ''
		for i in s:
			if i.isupper():
				u += i
			if i.islower():
				l += i
		u = ''.join(sorted(u))
		l = ''.join(sorted(l))
		n = len(u)
		m = len(l)
		i = 0
		g = min(n, m)
		t = ''
		while i < g:
			t += u[i] + l[i]
			i += 1
		while i < n:
			t += u[i]
			i += 1
		while i < m:
			t += l[i]
			i += 1
		return t


class Solution:

	def stringSort(self, s):
		l = []
		u = []
		for i in s:
			if i.isupper():
				u.append(i)
			else:
				l.append(i)
		l.sort()
		u.sort()
		ans = ''
		c = min(len(l), len(u))
		for i in range(c):
			ans += u[i]
			ans += l[i]
		for i in l[c:]:
			ans += i
		for i in u[c:]:
			ans += i
		return ans


class Solution:

	def stringSort(self, s):
		up = []
		lo = []
		for x in s:
			if x.isupper():
				up.append(x)
			else:
				lo.append(x)
		lo.sort()
		up.sort()
		if len(up) < len(lo):
			i = 0
			j = 0
			k = 0
			res = ''
			while j < len(up):
				if k % 2 == 0:
					res += up[j]
					j += 1
					k += 1
				else:
					res += lo[i]
					i += 1
					k += 1
			res = res + ''.join(lo[i:])
			return res
		elif len(lo) < len(up):
			i = 0
			j = 0
			k = 0
			res = ''
			while i < len(lo):
				if k % 2 == 0:
					res += up[j]
					j += 1
					k += 1
				else:
					res += lo[i]
					i += 1
					k += 1
			res = res + ''.join(up[j:])
			return res
		else:
			i = 0
			j = 0
			k = 0
			res = ''
			while j < len(up):
				if k % 2 == 0:
					res += up[j]
					j += 1
					k += 1
				else:
					res += lo[i]
					i += 1
					k += 1
			res = res + ''.join(lo[i:])
			return res


class Solution:

	def stringSort(self, s):
		(l, u) = ([], [])
		for char in s:
			if 97 <= ord(char) <= 122:
				l.append(char)
			if 65 <= ord(char) <= 90:
				u.append(char)
		l.sort()
		u.sort()
		ans = []
		for i in range(max(len(l), len(u))):
			if i < len(u):
				ans.append(u[i])
			if i < len(l):
				ans.append(l[i])
		return ''.join(ans)
t = int(input())
for tc in range(t):
	s = input()
	ob = Solution()
	print(ob.stringSort(s))


class Solution:

	def stringSort(self, s):
		S = ''
		sl = ''
		newS = ''
		for i in s:
			if i.isupper():
				S = S + i
			else:
				sl += i
		sl = ''.join(sorted(sl))
		S = ''.join(sorted(S))
		i = 0
		if len(S) >= len(sl):
			while i != len(sl):
				newS = newS + S[i] + sl[i]
				i += 1
			newS = newS + S[i:]
		elif len(sl) > len(S):
			while i != len(S):
				newS = newS + S[i] + sl[i]
				i += 1
			newS = newS + sl[i:]
		return newS


class Solution:

	def stringSort(self, s):
		s = list(s)
		s.sort()
		upper = ''
		lower = ''
		str = ''
		for ch in s:
			if ord(ch) <= 90:
				upper += ch
			else:
				lower += ch
		if len(upper) > len(lower):
			length = len(lower)
			left = upper[length:]
		else:
			length = len(upper)
			left = lower[length:]
		for i in range(length):
			str = str + upper[i] + lower[i]
		str += left
		return str


class Solution:

	def stringSort(self, s):
		s1 = ''
		s2 = ''
		ans = ''
		for i in s:
			if i.isupper():
				s1 += i
			else:
				s2 += i
		s1 = sorted(s1)
		s2 = sorted(s2)
		for i in range(len(s)):
			if len(s1) > i:
				ans += s1[i]
			if len(s2) > i:
				ans += s2[i]
		return ans


class Solution:

	def stringSort(self, s):
		low_string = []
		upper_string = []
		for i in range(0, len(s)):
			if s[i].islower() == True:
				low_string.append(s[i])
			else:
				upper_string.append(s[i])
		low_string.sort()
		upper_string.sort()
		k2 = [0] * len(s)
		i = 0
		j = 0
		k = 0
		while i < len(low_string) and j < len(upper_string):
			if k % 2 != 0:
				k2[k] = low_string[i]
				i = i + 1
				k = k + 1
			else:
				k2[k] = upper_string[i]
				k = k + 1
				j = j + 1
		while i < len(low_string):
			k2[k] = low_string[i]
			k = k + 1
			i = i + 1
		while j < len(upper_string):
			k2[k] = upper_string[j]
			k = k + 1
			j = j + 1
		return ''.join(k2)


class Solution:

	def stringSort(self, s):
		ans1 = ''
		ans2 = ''
		ans3 = ''
		flag = 0
		for i in s:
			if i.islower():
				ans1 = ans1 + i
			else:
				ans2 = ans2 + i
		ans1 = list(ans1)
		ans2 = list(ans2)
		ans1.sort()
		ans2.sort()
		sol1 = ''.join(ans1)
		sol2 = ''.join(ans2)
		l = min(len(sol1), len(sol2))
		j = 0
		while j < l:
			ans3 = ans3 + sol2[j]
			ans3 = ans3 + sol1[j]
			j += 1
		l = max(len(sol1), len(sol2))
		for i in range(j, l):
			if l == len(sol2):
				ans3 = ans3 + sol2[i]
			else:
				ans3 = ans3 + sol1[i]
		return ans3


class Solution:

	def stringSort(self, s):
		u = []
		l = []
		s1 = ''
		for i in s:
			if i >= 'a' and i <= 'z':
				l.append(i)
			else:
				u.append(i)
		l = sorted(l)
		u = sorted(u)
		if len(l) <= len(u):
			i = 0
			while i < len(l):
				s1 = s1 + u[i] + l[i]
				i = i + 1
			for j in range(i, len(u)):
				s1 = s1 + u[j]
		else:
			i = 0
			while i < len(u):
				s1 = s1 + u[i] + l[i]
				i = i + 1
			for j in range(i, len(l)):
				s1 = s1 + l[j]
		return s1


class Solution:

	def stringSort(self, s):
		output1 = ''
		output2 = ''
		output3 = ''
		for i in s:
			if i == i.lower():
				output2 += i
			else:
				output1 += i
		c = sorted(output1)
		d = sorted(output2)
		l = min(len(c), len(d))
		tx = ''
		i = 0
		while i < l:
			tx += c[i]
			tx += d[i]
			i += 1
		p = max(len(c), len(d))
		for j in range(i, p):
			if p == len(c):
				tx += c[j]
			else:
				tx += d[j]
		return tx


class Solution:

	def stringSort(self, s):
		asec_S = ''.join(sorted(s))
		small_letter = ''
		output = ''
		capital_letter = ''
		sorted_string = ''
		for i in asec_S:
			if len(s) == 1:
				output = s
				break
			elif i.istitle():
				capital_letter += i
			else:
				small_letter += i
		if not small_letter and (not capital_letter):
			return output
		elif not small_letter and capital_letter:
			output = ''.join(sorted(capital_letter))
		elif not capital_letter and small_letter:
			output = ''.join(sorted(small_letter))
		elif small_letter[0] > capital_letter[0]:
			s1 = capital_letter
			s2 = small_letter
			output = self.merge(s1, s2)
		elif small_letter[0] < capital_letter[0]:
			s1 = small_letter
			s2 = capital_letter
			output = self.merge(s1, s2)
		return output

	def merge(self, s1, s2):
		result = ''
		i = 0
		while i < len(s1) or i < len(s2):
			if i < len(s1):
				result += s1[i]
			if i < len(s2):
				result += s2[i]
			i += 1
		return result


class Solution:

	def stringSort(self, s):
		small = []
		capital = []
		for i in s:
			if i.isupper():
				capital.append(i)
			else:
				small.append(i)
		small.sort()
		capital.sort()
		res = ''
		m = min(len(small), len(capital))
		j = 0
		while j < m:
			res += capital[j] + small[j]
			j += 1
		M = max(len(small), len(capital))
		while j < M:
			if M == len(small):
				res += small[j]
			else:
				res += capital[j]
			j += 1
		return res


class Solution:

	def stringSort(self, s):
		u = []
		l = []
		for i in range(len(s)):
			if s[i].isupper():
				u.append(s[i])
			else:
				l.append(s[i])
		u.sort()
		l.sort()
		k = max(len(u), len(l))
		m = min(len(u), len(l))
		res = ''
		for i in range(m):
			res = res + u[i] + l[i]
		for i in range(m, k):
			if len(u) == k:
				res = res + u[i]
			else:
				res = res + l[i]
		return res


class Solution:

	def stringSort(self, s):
		upr = ''
		lwr = ''
		for el in s:
			if el.isupper():
				upr += el
			else:
				lwr += el
		upr = sorted(list(upr))
		lwr = sorted(list(lwr))
		res = ''
		i = 0
		j = 0
		while i + j < len(s):
			if i != len(upr):
				res += upr[i]
				i += 1
			if j != len(lwr):
				res += lwr[j]
				j += 1
		return res


class Solution:

	def stringSort(self, s):
		up = []
		do = []
		for i in s:
			a = ord(i)
			if a in range(65, 91):
				up.append(a)
			else:
				do.append(a)
		up.sort()
		do.sort()
		i = 0
		j = 0
		s = ''
		while i != len(up) and j != len(do):
			if i > j:
				s += chr(do[j])
				j += 1
			else:
				s += chr(up[i])
				i += 1
		while i != len(up):
			s += chr(up[i])
			i += 1
		while j != len(do):
			s += chr(do[j])
			j += 1
		return s


class Solution:

	def stringSort(self, s):
		l = []
		l1 = []
		for i in s:
			if i >= 'A' and i <= 'Z':
				l.append(i)
			else:
				l1.append(i)
		l.sort()
		l1.sort()
		ans = ''
		j = 0
		while j != max(len(l), len(l1)):
			if j < len(l):
				ans += l[j]
			if j < len(l1):
				ans += l1[j]
			j += 1
		return ans


class Solution:

	def stringSort(self, s):
		l = []
		l1 = []
		for i in s:
			if i >= 'A' and i <= 'Z':
				l.append(i)
			else:
				l1.append(i)
		l.sort()
		l1.sort()
		ans = ''
		for j in range(len(s)):
			if j < len(l):
				ans += l[j]
			if j < len(l1):
				ans += l1[j]
		return ans


class Solution:

	def stringSort(self, s):
		x = []
		y = []
		result = ''
		for i in s:
			if i.isupper():
				x.append(i)
			else:
				y.append(i)
		x.sort()
		y.sort()
		a = 0
		b = 0
		for i in range(len(s)):
			if a < len(x):
				result = result + x[a]
				a = a + 1
			if b < len(y):
				result = result + y[b]
				b = b + 1
		return result


class Solution:

	def stringSort(self, s):
		arrLow = []
		arrHigh = []
		for i in s:
			if i.islower():
				arrLow.append(i)
			else:
				arrHigh.append(i)
		arrLow.sort()
		arrHigh.sort()
		indexLow = 0
		indexHigh = 0
		newarr = ''
		toggle = 0
		while indexLow < len(arrLow) and indexHigh < len(arrHigh):
			if toggle == 0:
				newarr += arrHigh[indexHigh]
				toggle = 1
				indexHigh += 1
			else:
				newarr += arrLow[indexLow]
				toggle = 0
				indexLow += 1
		if indexLow < len(arrLow):
			while indexLow < len(arrLow):
				newarr += arrLow[indexLow]
				indexLow += 1
		if indexHigh < len(arrHigh):
			while indexHigh < len(arrHigh):
				newarr += arrHigh[indexHigh]
				indexHigh += 1
		return newarr