Given a string S consisting of only uppercase and lowercase characters. The task is to sort uppercase and lowercase letters separately such that if the i_{th} place in the original string had an Uppercase character then it should not have a lowercase character after being sorted and vice versa.
Example 1:
Input:
N = 12
S = defRTSersUXI
Output: deeIRSfrsTUX
Explanation: Sorted form of given string
with the same case of character as that
in original string is deeIRSfrsTUX
Example 2:
Input:
N = 6
S = srbDKi
Output: birDKs
Explanation: Sorted form of given string
with the same case of character will
result in output as birDKs.
Your Task:
You only need to complete the function caseSort that takes a string str and length of the string n and returns sorted string.
Expected Time Complexity: O(Nlog(N)).
Expected Auxiliary Space: O(N).
Constraints: 
1 ≤ N ≤ 10^{5}

Difficulty: MEDIUM
Tags: String algorithms

Sorting

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(Nlog(N)).
Expected Auxiliary Space: O(N).

Starter code:
#User function Template for python3



class Solution:



    #Function to perform case-specific sorting of strings.

    def caseSort(self,s,n):

        #code here

Solutions:
class Solution:

	def caseSort(self, s, n):
		d = ''
		(a, b) = ([], [])
		for i in range(n):
			if s[i].isupper():
				b.append(s[i])
			else:
				a.append(s[i])
		a = sorted(a)
		b = sorted(b)
		(j, k) = (0, 0)
		for i in s:
			if i.isupper():
				d += b[k]
				k += 1
			else:
				d += a[j]
				j += 1
		return d


class Solution:

	def caseSort(self, s, n):
		up = []
		lw = []
		for char in s:
			if char.isupper():
				up.append(char)
			else:
				lw.append(char)
		up.sort()
		lw.sort()
		ss = []
		up_i = 0
		lw_i = 0
		for char in s:
			if char.isupper():
				ss.append(up[up_i])
				up_i += 1
			else:
				ss.append(lw[lw_i])
				lw_i += 1
		return ''.join(ss)


class Solution:

	def caseSort(self, s, n):
		(ups, los, ans) = ([], [], [])
		for i in range(n):
			if s[i].islower() == True:
				los.append(s[i])
			else:
				ups.append(s[i])
		if los:
			los.sort()
		if ups:
			ups.sort()
		(x, y) = (0, 0)
		for i in range(n):
			if s[i].islower() == True:
				ans.append(los[x])
				x += 1
			else:
				ans.append(ups[y])
				y += 1
		return ''.join(ans)


class Solution:

	def caseSort(self, s, n):
		uppercase = []
		lowercase = []
		for char in s:
			if char.isupper():
				uppercase.append(char)
			else:
				lowercase.append(char)
		uppercase.sort()
		lowercase.sort()
		sorted_string = []
		uppercase_index = 0
		lowercase_index = 0
		for char in s:
			if char.isupper():
				sorted_string.append(uppercase[uppercase_index])
				uppercase_index += 1
			else:
				sorted_string.append(lowercase[lowercase_index])
				lowercase_index += 1
		return ''.join(sorted_string)


class Solution:

	def caseSort(self, s, n):
		s1 = ''
		s2 = ''
		arr = [0] * n
		for i in range(len(s)):
			c = s[i]
			if c.isupper():
				arr[i] = 2
				s2 = s2 + c
			else:
				arr[i] = 1
				s1 = s1 + c
		s1 = ''.join(sorted(s1))
		s2 = ''.join(sorted(s2))
		i = 0
		j = 0
		news = ''
		k = 0
		while i < len(s1) and j < len(s2) and (k < len(s)):
			if arr[k] == 1:
				news = news + s1[i]
				i = i + 1
			else:
				news = news + s2[j]
				j = j + 1
			k = k + 1
		while i < len(s1):
			news = news + s1[i]
			i = i + 1
		while j < len(s2):
			news = news + s2[j]
			j = j + 1
		return news


class Solution:

	def caseSort(self, s, n):
		lower = []
		upper = []
		ans = []
		for c in s:
			if c.islower():
				lower.append(c)
			else:
				upper.append(c)
		if lower:
			lower.sort()
		if upper:
			upper.sort()
		(x, y) = (0, 0)
		for i in range(n):
			if s[i].islower():
				ans.append(lower[x])
				x += 1
			else:
				ans.append(upper[y])
				y += 1
		return ''.join(ans)


class Solution:

	def caseSort(self, s, n):
		lower = [0 for _ in range(50)]
		upper = [0 for _ in range(50)]
		res = ''
		l = 0
		u = 0
		for character in s:
			if ord(character) >= ord('a') and ord(character) <= ord('z'):
				lower[abs(ord(character) - ord('a'))] += 1
			else:
				upper[abs(ord(character) - ord('A'))] += 1
		for i in range(n):
			if ord(s[i]) >= ord('a') and ord(s[i]) <= ord('z'):
				while lower[l] == 0:
					l += 1
				res += chr(ord('a') + l)
				lower[l] -= 1
			else:
				while upper[u] == 0:
					u += 1
				res += chr(ord('A') + u)
				upper[u] -= 1
		return res


class Solution:

	def caseSort(self, s, n):
		is_uppercase = [1 if c.isupper() else 0 for c in s]
		arr = sorted(s)
		k = 0
		for i in range(len(is_uppercase)):
			if is_uppercase[i] == 1:
				is_uppercase[i] = arr[k]
				k += 1
		for i in range(len(is_uppercase)):
			if is_uppercase[i] == 0:
				is_uppercase[i] = arr[k]
				k += 1
		return ''.join(is_uppercase)


class Solution:

	def caseSort(self, s, n):
		u = []
		l = []
		for i in s:
			if i.isupper():
				u.append(i)
			else:
				l.append(i)
		u.sort()
		l.sort()
		i = 0
		j = 0
		new = ''
		for x in range(len(s)):
			if s[x].isupper():
				new = new + u[i]
				i += 1
			else:
				new = new + l[j]
				j += 1
		return new


class Solution:

	def caseSort(self, s, n):
		sm = ''
		up = ''
		result = ''
		for i in s:
			if i.islower():
				sm += i
			else:
				up += i
		sm = sorted(sm)
		up = sorted(up)
		smi = upi = 0
		for i in s:
			if i.islower():
				result += sm[smi]
				smi += 1
			else:
				result += up[upi]
				upi += 1
		return result


class Solution:

	def caseSort(self, s, n):
		dic1 = {}
		dic2 = {}
		ans = []
		for ele in s:
			if ord(ele) < 97:
				if ele in dic1:
					dic1[ele] += 1
					continue
				dic1[ele] = 1
			else:
				if ele in dic2:
					dic2[ele] += 1
					continue
				dic2[ele] = 1
		dic3 = list(dic1.keys())
		dic4 = list(dic2.keys())
		dic3.sort()
		dic4.sort()
		i = 0
		j = 0
		for ele in s:
			if ord(ele) < 97:
				gle = dic3[i]
				if dic1[gle] > 1:
					ans.append(dic3[i])
					dic1[gle] -= 1
					continue
				ans.append(dic3[i])
				i += 1
			else:
				gle = dic4[j]
				if dic2[gle] > 1:
					ans.append(dic4[j])
					dic2[gle] -= 1
					continue
				ans.append(dic4[j])
				j += 1
		return ''.join(ans)


class Solution:

	def caseSort(self, s, n):
		lower = ''
		upper = ''
		for i in range(n):
			if s[i].isupper():
				upper += s[i]
			else:
				lower += s[i]
		lower = ''.join(sorted(lower))
		upper = ''.join(sorted(upper))
		x = 0
		y = 0
		result = ''
		for i in range(n):
			if s[i].isupper():
				result += upper[x]
				x += 1
			else:
				result += lower[y]
				y += 1
		return result


class Solution:

	def caseSort(self, s, n):
		(u, l, a) = ([], [], [])
		for i in range(n):
			if s[i].islower() == True:
				l.append(s[i])
			else:
				u.append(s[i])
		if l:
			l.sort()
		if u:
			u.sort()
		(x, y) = (0, 0)
		for i in range(n):
			if s[i].islower() == True:
				a.append(l[x])
				x += 1
			else:
				a.append(u[y])
				y += 1
		return ''.join(a)


class Solution:

	def caseSort(self, s, n):
		(arrUper, arrLower, ans) = ([], [], [])
		for i in range(n):
			if s[i].isupper():
				arrUper.append(s[i])
			else:
				arrLower.append(s[i])
		if len(arrUper):
			arrUper.sort()
		if len(arrLower):
			arrLower.sort()
		U = 0
		L = 0
		for i in range(n):
			if s[i].isupper():
				ans.append(arrUper[U])
				U += 1
			else:
				ans.append(arrLower[L])
				L += 1
		return ''.join(ans)


class Solution:

	def caseSort(self, S, n):
		upper = ''
		lower = ''
		for c in S:
			if c.isupper():
				upper += c
			else:
				lower += c
		upper_sorted = ''.join(sorted(upper))
		lower_sorted = ''.join(sorted(lower))
		result = ''
		i = 0
		j = 0
		for k in range(len(S)):
			if S[k].isupper():
				result += upper_sorted[i]
				i += 1
			else:
				result += lower_sorted[j]
				j += 1
		return result


class Solution:

	def caseSort(self, s, n):
		l = ''
		u = ''
		s1 = list(s)
		for i in s:
			if i.islower() == True:
				l = l + i
			else:
				u = u + i
		l1 = sorted(l)
		u1 = sorted(u)
		j = 0
		k = 0
		for i in range(len(s1)):
			if s1[i].islower() == True:
				s1[i] = l1[j]
				j = j + 1
			else:
				s1[i] = u1[k]
				k = k + 1
		return ''.join(s1)


class Solution:

	def caseSort(self, s, n):
		upper = []
		lower = []
		for i in s:
			if ord(i) >= 65 and ord(i) <= 90:
				upper.append(i)
			else:
				lower.append(i)
		upper.sort()
		lower.sort()
		i = 0
		j = 0
		n1 = len(upper)
		n2 = len(lower)
		s1 = ''
		for k in range(n):
			if ord(s[k]) >= 65 and ord(s[k]) <= 90:
				s1 += upper[i]
				i += 1
			else:
				s1 += lower[j]
				j += 1
		return s1


class Solution:

	def caseSort(self, s, n):
		s1 = ''
		s2 = ''
		for i in range(n):
			if ord(s[i]) >= 97:
				s1 += s[i]
			else:
				s2 += s[i]
		s1 = list(sorted(s1))
		s2 = list(sorted(s2))
		ans = ''
		j = 0
		k = 0
		while j + k < n - 1:
			for i in range(n):
				if ord(s[i]) >= 97:
					ans += s1[j]
					j += 1
				else:
					ans += s2[k]
					k += 1
		return ans


class Solution:

	def caseSort(self, s, n):
		up = []
		low = []
		for i in range(len(s)):
			if s[i].isupper():
				up.append(s[i])
			else:
				low.append(s[i])
		(u, l) = (0, 0)
		up.sort()
		low.sort()
		j = 0
		ans = []
		while j < len(s):
			if s[j].isupper():
				ans.append(up[u])
				u += 1
			else:
				ans.append(low[l])
				l += 1
			j += 1
		return ''.join(ans)


class Solution:

	def caseSort(self, s, n):
		s1 = []
		s2 = []
		l = 0
		h = n - 1
		for i in range(0, n):
			if s[i].islower():
				s1.append(s[i])
			else:
				s2.append(s[i])
		s1.sort()
		s2.sort()
		(i1, j) = (0, 0)
		s11 = ''
		for i in range(0, n):
			if s[i].islower() and i1 < len(s1):
				s11 = s11 + s1[i1]
				i1 = i1 + 1
			elif s[i].isupper() and j < len(s2):
				s11 = s11 + s2[j]
				j = j + 1
		return s11


class Solution:

	def caseSort(self, s, n):
		lower = []
		upper = []
		new_lst = []
		for i in s:
			if i.isupper():
				upper += [i]
			else:
				lower += [i]
		lower.sort()
		upper.sort()
		i = j = k = 0
		while i < len(lower) and j < len(upper) and (k < len(s)):
			if s[k].islower():
				new_lst.append(lower[i])
				i += 1
			elif s[k].isupper():
				new_lst.append(upper[j])
				j += 1
			k += 1
		while i < len(lower):
			new_lst += [lower[i]]
			i += 1
		while j < len(upper):
			new_lst += [upper[j]]
			j += 1
		return ''.join(new_lst)


class Solution:

	def caseSort(self, s, n):
		s1 = s
		upper = ''
		lower = ''
		for c in s1:
			if c >= 'A' and c <= 'Z':
				upper += c
			else:
				lower += c
		lower = sorted(lower)
		upper = sorted(upper)
		i = 0
		j = 0
		result = ''
		for ch in range(len(s1)):
			if s1[ch] >= 'A' and s1[ch] <= 'Z':
				result += upper[i]
				i += 1
			elif s1[ch] >= 'a' and s1[ch] <= 'z':
				result += lower[j]
				j += 1
		return result


class Solution:

	def caseSort(self, s, n):
		u = []
		l = []
		for i in s:
			if i.isupper():
				u.append(i)
			else:
				l.append(i)
		u = sorted(u)
		l = sorted(l)
		p = ''
		i = 0
		j = 0
		for k in s:
			if k.isupper():
				p += u[i]
				i += 1
			else:
				p += l[j]
				j += 1
		return p


class Solution:

	def caseSort(self, s, n):
		lower = []
		upper = []
		for w in s:
			if w.islower():
				lower.append(w)
			else:
				upper.append(w)
		ret = ''
		l = 0
		u = 0
		lower.sort()
		upper.sort()
		for w in s:
			if w.islower():
				ret += lower[l]
				l += 1
			else:
				ret += upper[u]
				u += 1
		return ret


class Solution:

	def caseSort(self, s, n):
		x = sorted(s, reverse=True)
		m = n - 1
		i = 0
		while i < n:
			if ord(x[i]) < 97:
				break
			else:
				i += 1
		newstr = ''
		low = 0
		high = i
		while low < i or high < n:
			if ord(s[m]) < 97:
				newstr = x[high] + newstr
				high += 1
				m -= 1
			else:
				newstr = x[low] + newstr
				low += 1
				m -= 1
		while low < i:
			newstr = x[low] + newstr
			low += 1
		while high < n:
			newstr = x[high] + newstr
			high += 1
		return newstr


class Solution:

	def caseSort(self, s, n):
		uppercase = ''
		lowercase = ''
		string = ''
		for i in s:
			if ord(i) > 64 and ord(i) < 91:
				uppercase += i
			if ord(i) > 96 and ord(i) < 123:
				lowercase += i
		uppercase = sorted(uppercase)
		lowercase = sorted(lowercase)
		i = 0
		j = 0
		for k in s:
			if ord(k) > 64 and ord(k) < 91:
				string += uppercase[i]
				i += 1
			if ord(k) > 96 and ord(k) < 123:
				string += lowercase[j]
				j += 1
		return string


class Solution:

	def caseSort(self, s, n):
		uppers = []
		lowers = []
		ans = []
		for c in s:
			if c.islower():
				lowers.append(c)
			else:
				uppers.append(c)
		uppers.sort()
		lowers.sort()
		ui = 0
		li = 0
		for i in range(n):
			if s[i].islower():
				ans.append(lowers[li])
				li += 1
			else:
				ans.append(uppers[ui])
				ui += 1
		return ''.join(ans)


class Solution:

	def caseSort(self, s, n):
		l = []
		u = []
		for i in s:
			if i.islower():
				l.append(i)
			else:
				u.append(i)
		new = ''
		l_index = 0
		u_index = 0
		l.sort()
		u.sort()
		for i in s:
			if i.isupper():
				new += u[u_index]
				u_index += 1
			else:
				new += l[l_index]
				l_index += 1
		return new


class Solution:

	def caseSort(self, s, n):
		l = []
		u = []
		for i in s:
			if i.islower() == True:
				l.append(i)
			else:
				u.append(i)
		l.sort()
		u.sort()
		le = 0
		ue = 0
		res = ''
		for i in range(n):
			if s[i].islower() == True:
				res = res + l[le]
				le = le + 1
			else:
				res = res + u[ue]
				ue = ue + 1
		res.lstrip()
		return res


class Solution:

	def caseSort(self, s, n):
		finalString = ''
		str1 = ''.join(sorted([i if ord(i) > 64 and ord(i) < 91 else '' for i in s]))
		str2 = ''.join(sorted([i if ord(i) > 96 and ord(i) < 123 else '' for i in s]))
		i = 0
		j = 0
		for k in s:
			if ord(k) > 64 and ord(k) < 91:
				finalString += str1[i]
				i += 1
			if ord(k) > 96 and ord(k) < 123:
				finalString += str2[j]
				j += 1
		return finalString


class Solution:

	def caseSort(self, s, n):
		(li1, li2, st, c1, c2) = ([], [], '', 0, 0)
		for i in s:
			if 'a' <= i <= 'z':
				li1 += [i]
			else:
				li2 += [i]
		li1.sort()
		li2.sort()
		for i in s:
			if 'a' <= i <= 'z':
				st += li1[c1]
				c1 += 1
			else:
				st += li2[c2]
				c2 += 1
		return st


class Solution:

	def caseSort(self, s, n):
		s = list(s)
		u = []
		l = []
		for i in range(len(s)):
			if ord(s[i]) >= 65 and ord(s[i]) <= 90:
				u.append(s[i])
			elif ord(s[i]) >= 97 and ord(s[i]) <= 122:
				l.append(s[i])
		u = sorted(u)
		l = sorted(l)
		u = u[::-1]
		l = l[::-1]
		t = ''
		for j in range(len(s)):
			if ord(s[j]) >= 65 and ord(s[j]) <= 90:
				t = t + u.pop()
			elif ord(s[j]) >= 97 and ord(s[j]) <= 122:
				t = t + l.pop()
		return t


class Solution:

	def caseSort(self, s, n):
		(u, l) = ('', '')
		res = ''
		for i in s:
			if i.isupper():
				u += i
			else:
				l += i
		u = sorted(u)
		l = sorted(l)
		(x, y) = (0, 0)
		for (j, i) in enumerate(s):
			if i.isupper():
				res += u[x]
				x += 1
			else:
				res += l[y]
				y += 1
		return res


class Solution:

	def caseSort(self, s, n):
		a = []
		b = []
		for i in s:
			if i.isupper():
				a.append(i)
			else:
				b.append(i)
		a.sort()
		b.sort()
		i = 0
		j = 0
		r = ''
		for k in range(n):
			if s[k].isupper():
				r += a[i]
				i += 1
			else:
				r += b[j]
				j += 1
		return r


class Solution:

	def caseSort(self, s, n):
		if len(s) == 0:
			return ''
		if len(s) == 1:
			return s
		li = list(s)
		i = 0
		j = 0
		k = 0
		m = 0
		s1 = ''
		li.sort()
		while i < n and j <= n and (k < n):
			if (ord(s[k]) > 64 and ord(s[k]) < 91) and (ord(li[i]) > 96 and ord(li[i]) < 123):
				i += 1
			elif (ord(s[k]) > 96 and ord(s[k]) < 123) and (ord(li[j]) > 64 and ord(li[j]) < 91):
				j += 1
			elif (ord(s[k]) > 64 and ord(s[k]) < 91) and (ord(li[i]) > 64 and ord(li[i]) < 91):
				s1 += li[i]
				i += 1
				k += 1
			else:
				s1 += li[j]
				j += 1
				k += 1
		return s1


class Solution:

	def caseSort(self, s, n):
		u = 0
		ans = ''
		a = []
		l = 0
		for i in range(n):
			if s[i].isupper():
				u += 1
			else:
				l += 1
			a.append(s[i])
		a.sort()
		j = 0
		k = u
		for i in range(n):
			if s[i].isupper():
				ans += a[j]
				j += 1
			else:
				ans += a[k]
				k += 1
		return ans


class Solution:

	def caseSort(self, s, n):
		lst1 = []
		lst2 = []
		for i in range(n):
			if s[i].isupper():
				lst1.append(s[i])
			else:
				lst2.append(s[i])
		lst1.sort()
		lst2.sort()
		empty_str = ''
		a = b = 0
		for i in range(n):
			if s[i].isupper():
				empty_str = empty_str + lst1[a]
				a = a + 1
			else:
				empty_str = empty_str + lst2[b]
				b = b + 1
		return empty_str


class Solution:

	def caseSort(self, s, n):
		l = []
		s1 = ''
		s2 = ''
		for i in range(len(s)):
			if s[i].islower():
				l.append(0)
				s1 += s[i]
			else:
				l.append(1)
				s2 += s[i]
		x1 = ''.join(sorted(s1))
		x2 = ''.join(sorted(s2))
		y = 0
		z = 0
		S = ''
		for i in range(len(s)):
			if l[i] == 0:
				S += x1[y]
				y = y + 1
			else:
				S += x2[z]
				z = z + 1
		return S


class Solution:

	def caseSort(self, s, n):
		uCase = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
		lCase = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
		u_buf = list()
		l_buf = list()
		for c in range(n):
			if s[c] in uCase:
				u_buf.append(c)
			else:
				l_buf.append(c)
		u_lst = [s[i] for i in u_buf]
		l_lst = [s[i] for i in l_buf]
		u_lst.sort()
		l_lst.sort()
		ans = ['' for i in range(n)]
		for i in range(len(u_lst)):
			ans[u_buf[i]] = u_lst[i]
		for i in range(len(l_lst)):
			ans[l_buf[i]] = l_lst[i]
		return ''.join(ans)


class Solution:

	def caseSort(self, s, n):
		(upp, loww) = ('', '')
		for i in s:
			if i.islower() == True:
				loww += i
			else:
				upp += i
		low = sorted(loww)
		up = sorted(upp)
		res = ''
		x = 0
		y = 0
		for i in range(n):
			if s[i].islower() == True:
				res += low[x]
				x += 1
			else:
				res += up[y]
				y += 1
		return res


class Solution:

	def caseSort(self, s, n):
		(Lower, Upper, result) = ([], [], [])
		(m, k) = (0, 0)
		for i in range(n):
			if s[i].isupper():
				Upper.append(s[i])
			elif s[i].islower():
				Lower.append(s[i])
		Upper.sort()
		Lower.sort()
		for i in range(n):
			if s[i].isupper():
				result.append(Upper[m])
				m += 1
			elif s[i].islower():
				result.append(Lower[k])
				k += 1
		return ''.join(result)


class Solution:

	def caseSort(self, s, n):
		s1 = []
		s2 = []
		for i in range(n):
			if s[i] >= 'a' and s[i] <= 'z':
				s1.append(s[i])
			else:
				s2.append(s[i])
		s1 = sorted(s1)
		s2 = sorted(s2)
		i = 0
		j = 0
		s = list(s)
		for k in range(n):
			if s[k] >= 'a' and s[k] <= 'z':
				s[k] = s1[i]
				i = i + 1
			else:
				s[k] = s2[j]
				j = j + 1
		return ''.join(s)


class Solution:

	def caseSort(self, s, n):
		(l, u) = ([], [])
		for i in s:
			if i.isupper():
				u.append(i)
			else:
				l.append(i)
		l = sorted(l)
		u = sorted(u)
		res = ''
		a = 0
		b = 0
		for i in s:
			if i.islower():
				res += l[a]
				a += 1
			else:
				res += u[b]
				b += 1
		return ''.join(res)


class Solution:

	def caseSort(self, s, n):
		(up, lw, res) = ([], [], [])
		for i in range(n):
			if s[i].islower() == True:
				lw.append(s[i])
			else:
				up.append(s[i])
		if lw:
			lw.sort()
		if up:
			up.sort()
		(x, y) = (0, 0)
		for i in range(n):
			if s[i].islower() == True:
				res.append(lw[x])
				x += 1
			else:
				res.append(up[y])
				y += 1
		return ''.join(res)


class Solution:

	def caseSort(self, s, n):
		v1 = []
		v2 = []
		s1 = ''
		for i in range(n):
			if s[i] >= 'a' and s[i] <= 'z':
				v1.append(s[i])
			if s[i] >= 'A' and s[i] <= 'Z':
				v2.append(s[i])
		v1 = sorted(v1)
		v2 = sorted(v2)
		i = 0
		j = 0
		for k in range(n):
			if s[k] >= 'a' and s[k] <= 'z':
				s1 += v1[i]
				i += 1
			elif s[k] >= 'A' and s[k] <= 'Z':
				s1 += v2[j]
				j += 1
		return s1


class Solution:

	def caseSort(self, s, n):
		l = []
		u = []
		for i in s:
			if i.islower():
				l.append(i)
			else:
				u.append(i)
		l = sorted(l)
		u = sorted(u)
		res = ''
		j = k = 0
		for i in s:
			if i.islower():
				res += l[j]
				j += 1
			else:
				res += u[k]
				k += 1
		return res


from collections import deque

class Solution:

	def caseSort(self, s, n):
		upper = list()
		lower = list()
		answer = ''
		for ch in s:
			if ch <= 'Z':
				upper.append(ch)
			else:
				lower.append(ch)
		upper.sort()
		lower.sort()
		upper = deque(upper)
		lower = deque(lower)
		for i in range(n):
			if s[i] <= 'Z':
				answer += upper.popleft()
			else:
				answer += lower.popleft()
		return answer


class Solution:

	def caseSort(self, s, n):
		res = [0 for each in range(len(s))]
		(caps, cap_ind, low, low_ind) = ([], [], [], [])
		for i in range(len(s)):
			if 97 <= ord(s[i]) <= 122:
				low.append(s[i])
				low_ind.append(i)
			elif 65 <= ord(s[i]) <= 90:
				caps.append(s[i])
				cap_ind.append(i)
		low.sort()
		caps.sort()
		for (chr1, ind1) in zip(low, low_ind):
			res[ind1] = chr1
		for (chr2, ind2) in zip(caps, cap_ind):
			res[ind2] = chr2
		ans = ''
		for each in res:
			ans += each
		return ans


class Solution:

	def caseSort(self, S, n):
		a = []
		b = []
		c = ' '
		a = [i for i in S if i.islower()]
		b = [i for i in S if i.isupper()]
		c = sorted(a)
		d = sorted(b)
		e = ''
		i = 0
		j = 0
		for k in S:
			if k.islower():
				e += c[i]
				i = i + 1
			else:
				e += d[j]
				j = j + 1
		return e


class Solution:

	def caseSort(self, s, n):
		tempstr = ['0'] * n
		for i in range(0, len(s)):
			if s[i].islower():
				tempstr[i] = '0'
			else:
				tempstr[i] = '1'
		small = ''
		cap = ''
		for i in s:
			if i.islower():
				small += i
			else:
				cap += i
		slist = sorted(small)
		small = ''.join(slist)
		clist = sorted(cap)
		cap = ''.join(clist)
		k = 0
		l = 0
		ns = ''
		for i in range(0, len(s)):
			if tempstr[i] == '0':
				ns += small[k]
				k += 1
			else:
				ns += cap[l]
				l += 1
		return ns


class Solution:

	def caseSort(self, s, n):
		S1 = [''] * n
		a = []
		b = []
		for i in s:
			if i.islower():
				a.append(i)
			else:
				b.append(i)
		a.sort()
		b.sort()
		low = 0
		up = 0
		for i in range(n):
			if s[i].islower():
				S1[i] = a[low]
				low += 1
			else:
				S1[i] = b[up]
				up += 1
		return ''.join(S1)


class Solution:

	def caseSort(self, s, n):
		upper = ''
		lower = ''
		for c in s:
			if c.isupper():
				upper += c
			elif c.islower():
				lower += c
		upper = ''.join(sorted(upper))
		lower = ''.join(sorted(lower))
		result = ''
		p1 = p2 = 0
		for c in s:
			if c.isupper():
				result += upper[p1]
				p1 += 1
			elif c.islower():
				result += lower[p2]
				p2 += 1
			else:
				result += c
		return result


class Solution:

	def caseSort(self, s, n):
		l1 = []
		l2 = []
		l = []
		for i in range(n):
			if s[i].isupper():
				l1.append(s[i])
			else:
				l2.append(s[i])
		j = 0
		k = 0
		l1.sort()
		l2.sort()
		for i in range(n):
			if s[i].isupper():
				l.append(l1[j])
				j = j + 1
			else:
				l.append(l2[k])
				k = k + 1
		return ''.join(l)


class Solution:

	def caseSort(self, s, n):
		list1 = []
		list2 = []
		list3 = []
		for i in s:
			if i.isupper():
				list1.append(i)
			if i.islower():
				list2.append(i)
		list1.sort()
		list2.sort()
		j = 0
		k = 0
		for i in s:
			if i.isupper():
				list3.append(list1[j])
				j += 1
			if i.islower():
				list3.append(list2[k])
				k += 1
		l = ''.join(list3)
		return l