Given a string arr consisting of lowercase english letters, arrange all its letters in lexicographical order using Counting Sort.
Example 1:
Input:
N = 5
S = "edsab"
Output:
abdes
Explanation: 
In lexicographical order, string will be 
abdes.
Example 2:
Input:
N = 13
S = "geeksforgeeks"
Output:
eeeefggkkorss
Explanation:
In lexicographical order, string will be 
eeeefggkkorss.
Your Task:
This is a function problem. You only need to complete the function countSort() that takes string arr as a parameter and returns the sorted string. The printing is done by the driver code.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 10^{5}
Video:

Difficulty: EASY
Tags: Sorting
Skill types: Sorting
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Starter code:
#User function Template for python3



class Solution:

    #Function to arrange all letters of a string in lexicographical 

    #order using Counting Sort.

    def countSort(self,arr):

        # code here

Solutions:
class Solution:

	def countSort(self, arr):
		cnt = [0] * 26
		for i in arr:
			cnt[ord(i) - 97] += 1
		ans = ''
		for i in range(len(cnt)):
			while cnt[i] > 0:
				ans += chr(i + 97)
				cnt[i] -= 1
		return ans


class Solution:

	def countSort(self, arr):
		count = [0] * 26
		out = [0] * len(arr)
		for k in arr:
			count[ord(k) - ord('a')] += 1
		for i in range(1, len(count)):
			count[i] += count[i - 1]
		for k in arr:
			out[count[ord(k) - ord('a')] - 1] = k
			count[ord(k) - ord('a')] -= 1
		return ''.join(out)


class Solution:

	def countSort(self, arr):
		arr1 = list(arr)
		arr1.sort()
		arr = ''.join(arr1)
		return arr


class Solution:

	def _order(self, ch):
		return ord(ch) - ord('a')

	def _ch(self, _ord):
		return chr(ord('a') + _ord)

	def countSort(self, arr):
		count_arr = [0] * 26
		for ch in arr:
			count_arr[self._order(ch)] += 1
		a_idx = 0
		arr = []
		for (idx, count) in enumerate(count_arr):
			ch = self._ch(idx)
			for i in range(count):
				arr.append(ch)
		return ''.join(arr)


class Solution:

	def countSort(self, arr):
		l = len(arr)
		dp = [0] * 26
		ans = [0] * l
		for i in arr:
			val = ord(i) - ord('a')
			dp[val] += 1
		for i in range(1, 26):
			dp[i] = dp[i - 1] + dp[i]
		for i in range(l - 1, -1, -1):
			val = ord(arr[i]) - ord('a')
			curr = dp[val]
			ans[curr - 1] = arr[i]
			dp[val] -= 1
		an = ''
		for i in range(l):
			an += ans[i]
		return an


class Solution:

	def countSort(self, arr):
		ar = []
		for i in arr:
			ar.append(i)
		ar.sort()
		ans = ''
		for i in range(len(ar)):
			ans += ar[i]
		return ans


class Solution:

	def countSort(self, arr):
		t = ''
		s = sorted(arr)
		for x in s:
			t += x
		return t


class Solution:

	def countSort(self, arr):
		lst = []
		for i in range(0, 26):
			lst.append(0)
		for i in arr:
			lst[ord(i) - 97] += 1
		arr = ''
		for i in range(0, len(lst)):
			while lst[i] > 0:
				arr += chr(97 + i)
				lst[i] -= 1
		return arr


class Solution:

	def countSort(self, arr):
		arr = sorted(arr)
		a = ''.join(arr)
		return a


class Solution:

	def countSort(self, arr):
		s = sorted(arr)
		j = ''.join(s)
		return j


class Solution:

	def countSort(self, arr):
		output = [0] * len(arr)
		count_arr = [0] * 265
		for i in arr:
			count_arr[ord(i)] = count_arr[ord(i)] + 1
		for i in range(1, len(count_arr)):
			count_arr[i] = count_arr[i] + count_arr[i - 1]
		for i in arr:
			output[count_arr[ord(i)] - 1] = i
			count_arr[ord(i)] = count_arr[ord(i)] - 1
		return ''.join(output)


class Solution:

	def countSort(self, arr):
		lis = list(arr)
		lis.sort()
		str1 = ''
		for i in lis:
			str1 += i
		return str1


class Solution:

	def countSort(self, arr):
		s = ''
		lst = [arr[i] for i in range(0, len(arr))]
		lst.sort()
		for i in lst:
			s += i
		return s


class Solution:

	def countSort(self, arr):
		freq = [0] * 26
		for ch in arr:
			idx = ord(ch) - ord('a')
			freq[idx] += 1
		ans = ''
		for i in range(26):
			if freq[i] > 0:
				for k in range(freq[i]):
					ans += chr(97 + i)
		return ans


class Solution:

	def countSort(self, a):
		b = []
		for i in a:
			b.append(i)
		b.sort()
		return ''.join(b)


class Solution:

	def countSort(self, arr):
		output = [0 for i in range(len(arr))]
		count = [0 for i in range(256)]
		ans = ''
		for i in arr:
			count[ord(i)] += 1
		for i in range(256):
			count[i] += count[i - 1]
		for i in range(len(arr)):
			output[count[ord(arr[i])] - 1] = arr[i]
			count[ord(arr[i])] -= 1
		for i in range(len(arr)):
			ans = ans + output[i]
		return ans


class Solution:

	def countSort(self, arr):
		count = [0] * 26
		for x in arr:
			count[ord(x) - 97] += 1
		res = []
		for i in range(26):
			if count[i] != 0:
				while count[i] > 0:
					res.append(chr(i + 97))
					count[i] -= 1
		return ''.join(res)


class Solution:

	def countSort(self, arr):
		li = [0 for i in range(0, 27)]
		for i in arr:
			li[ord(i) - 96] += 1
		for i in range(1, len(li)):
			li[i] = li[i] + li[i - 1]
		ans = [0 for i in range(len(arr) + 1)]
		for j in range(len(arr)):
			if li[ord(arr[j]) - 96] != 0:
				ans[li[ord(arr[j]) - 96]] = chr(ord(arr[j]))
				li[ord(arr[j]) - 96] -= 1
		st = ''
		for i in ans:
			if i != 0:
				st += i
		return st


class Solution:

	def countSort(self, arr):
		sorted_str = ''.join(sorted(arr))
		return sorted_str


class Solution:

	def countSort(self, arr):
		hs = [0 for x in range(27)]
		ans = ['' for x in range(len(arr))]
		st = ''
		for x in arr:
			hs[ord(x) - 96] += 1
		for x in range(1, len(hs)):
			hs[x] += hs[x - 1]
		for x in arr:
			ans[hs[ord(x) - 96] - 1] = x
			hs[ord(x) - 96] -= 1
		for x in ans:
			st += str(x)
		return st


class Solution:

	def countSort(self, p):
		p = list(p.strip(''))
		p.sort()
		p = ''.join(p)
		return p


class Solution:

	def countSort(self, arr):
		arr = sorted(arr)
		arr = ''.join(arr)
		return arr.replace(',', '')


class Solution:

	def countSort(self, arr):
		a = list(arr)
		a.sort()
		s = ''
		for i in a:
			s += i
		return s


class Solution:

	def countSort(self, arr):
		count = [0] * 26
		for char in arr:
			count[ord(char) - ord('a')] += 1
		for i in range(1, 26):
			count[i] += count[i - 1]
		output = [''] * len(arr)
		for char in reversed(arr):
			index = count[ord(char) - ord('a')] - 1
			output[index] = char
			count[ord(char) - ord('a')] -= 1
		return ''.join(output)


class Solution:

	def countSort(self, arr):
		l = [0] * 26
		for i in range(len(arr)):
			x = ord(arr[i]) - 97
			l[x] += 1
		res = ''
		for i in range(len(l)):
			for j in range(l[i]):
				res += chr(i + 97)
		return res


class Solution:

	def countSort(self, arr):
		s = list(arr)
		x = sorted(s)
		ans = ''.join(x)
		return ans


class Solution:

	def countSort(self, arr):
		count = [0] * 26
		res = ''
		for item in arr:
			idx = ord(item) - 97
			count[idx] += 1
		for i in range(len(count)):
			while count[i] != 0:
				res += chr(i + 97)
				count[i] -= 1
		return res


class Solution:

	def countSort(self, arr):
		t = [0] * 26
		for c in arr:
			t[ord(c) - ord('a')] += 1
		res = list(arr)
		for i in range(1, 26):
			t[i] += t[i - 1]
		for c in reversed(arr):
			res[t[ord(c) - ord('a')] - 1] = c
			t[ord(c) - ord('a')] -= 1
		ress = ''.join(res)
		return ress


class Solution:

	def countSort(self, arr):
		t = [0] * 26
		for c in arr:
			t[ord(c) - ord('a')] += 1
		res = ''
		for i in range(26):
			res += ''.join((chr(i + ord('a')) for j in range(t[i])))
		return res


class Solution:

	def countSort(self, arr):
		mini = ord('a')
		maxi = ord('z')
		farr = [0 for i in range(maxi - mini + 1)]
		ans = [0 for i in range(len(arr))]
		for i in range(len(arr)):
			idx = ord(arr[i]) - mini
			farr[idx] += 1
		farr[0] -= 1
		for i in range(1, len(farr)):
			farr[i] += farr[i - 1]
		for i in range(len(arr) - 1, -1, -1):
			pos = farr[ord(arr[i]) - mini]
			ans[pos] = arr[i]
			farr[ord(arr[i]) - mini] -= 1
		arr1 = ''
		for i in range(len(ans)):
			arr1 = arr1 + str(ans[i])
		return arr1


class Solution:

	def countSort(self, arr):

		def counting_sort(llist):
			counter = [0 for x in range(26)]
			result = []
			for num in llist:
				counter[num] += 1
			for (ind, value) in enumerate(counter):
				for i in range(value):
					result.append(ind)
			return result
		lis = [ord(x) - 97 for x in arr]
		lis = counting_sort(lis)
		strg = ''.join([chr(y + 97) for y in lis])
		return strg


class Solution:

	def countSort(self, arr):
		c = [0] * 26
		for i in arr:
			c[ord(i) - ord('a')] += 1
		res = ''
		for i in range(26):
			while c[i] != 0:
				res += chr(i + ord('a'))
				c[i] -= 1
		return res


class Solution:

	def solve(self, arr):
		count_arr = [0] * 26
		sorted_arr = [0] * len(arr)
		for i in range(len(arr)):
			count_arr[arr[i]] += 1
		s = 0
		for i in range(len(count_arr)):
			s += count_arr[i]
			count_arr[i] = s
		i = len(arr) - 1
		while i >= 0:
			sorted_arr[count_arr[arr[i]] - 1] = arr[i]
			count_arr[arr[i]] -= 1
			i -= 1
		return sorted_arr

	def intTostr(self, arr):
		s = ''
		for i in range(len(arr)):
			s += chr(arr[i] + 97)
		return s

	def countSort(self, arr):
		arr2 = []
		for i in range(len(arr)):
			arr2.append(ord(arr[i]) - 97)
		arr2 = self.solve(arr2)
		return self.intTostr(arr2)


class Solution:

	def countSort(self, arr):
		count = [0] * 26
		for letter in arr:
			count[ord(letter) - ord('a')] += 1
		sorted_arr = ''
		for i in range(26):
			sorted_arr += count[i] * chr(i + ord('a'))
		return sorted_arr


class Solution:

	def countSort(self, arr):
		l = []
		for i in arr:
			l.append(i)
		l.sort()
		word = ''
		for wrd in l:
			word += wrd
		return word


class Solution:

	def countSort(self, arr):
		count = [0] * 26
		for char in arr:
			count[ord(char) - ord('a')] += 1
		for i in range(1, 26):
			count[i] += count[i - 1]
		sorted_arr = [''] * len(arr)
		for char in arr:
			sorted_arr[count[ord(char) - ord('a')] - 1] = char
			count[ord(char) - ord('a')] -= 1
		return ''.join(sorted_arr)


class Solution:

	def countSort(self, arr):
		l = []
		l[:0] = arr
		return ''.join(sorted(l))


class Solution:

	def countSort(self, arr):
		a = ''
		b = sorted(arr)
		for i in b:
			a += i
		return a


class Solution:

	def countSort(self, arr):
		ls = list(arr.strip(''))
		ls.sort()
		ls = ''.join(ls)
		return ls


class Solution:

	def countSort(self, arr):
		l = list(arr.strip(''))
		l.sort()
		l = ''.join(l)
		return l


class Solution:

	def countSort(self, arr):
		max_el = ord(max(list(arr)))
		arr = [ord(i) for i in arr]
		temp_arr = [0] * (max_el + 1)
		for i in arr:
			temp_arr[i] += 1
		for i in range(1, len(temp_arr)):
			temp_arr[i] += temp_arr[i - 1]
		max_el = max(temp_arr)
		sorted_arr = [0] * max_el
		for i in arr:
			count = temp_arr[i]
			sorted_arr[count - 1] = i
			temp_arr[i] -= 1
		return ''.join((chr(s) for s in sorted_arr))
		print(temp_arr)


class Solution:

	def countSort(self, arr):
		count = [0] * 26
		for l in arr:
			count[ord(l) - 97] += 1
		for i in range(25):
			count[i + 1] += count[i]
		ans = [0] * len(arr)
		for l in arr[::-1]:
			ans[count[ord(l) - 97] - 1] = l
			count[ord(l) - 97] -= 1
		return ''.join(ans)


class Solution:

	def countSort(self, arr):
		temp = list(arr)
		temp.sort()
		return ''.join(temp)


class Solution:

	def countSort(self, arr):
		L = []
		for i in arr:
			L.append(i)
		L.sort()
		s = ''.join(L)
		return s


class Solution:

	def countSort(self, arr):
		op = [0 for i in range(len(arr))]
		index = [0 for i in range(256)]
		result = [0 for i in range(len(arr))]
		for i in range(len(arr)):
			index[ord(arr[i])] += 1
		for i in range(1, 256):
			index[i] += index[i - 1]
		for i in range(len(arr) - 1, -1, -1):
			result[index[ord(arr[i])] - 1] = arr[i]
			index[ord(arr[i])] -= 1
		for i in range(len(arr)):
			op[i] = result[i]
		res = ''.join(op)
		return res


class Solution:

	def countSort(self, arr):
		temp = [0] * 26
		for c in arr:
			temp[ord(c) - ord('a')] += 1
		for i in range(1, 26):
			temp[i] += temp[i - 1]
		output = [''] * len(arr)
		for i in range(len(arr) - 1, -1, -1):
			output[temp[ord(arr[i]) - ord('a')] - 1] = arr[i]
			temp[ord(arr[i]) - ord('a')] -= 1
		return ''.join(output)


class Solution:

	def countSort(self, arr):
		a = list(arr)
		a.sort()
		a = ''.join(a)
		return a


class Solution:

	def countSort(self, arr):
		str_arr = ''.join(arr)
		list_arr = list(str_arr)
		list_arr.sort()
		str_arr = ''.join(list_arr)
		return str_arr


class Solution:

	def countSort(self, arr):
		c = ''
		count = [0] * 256
		for i in arr:
			if count[ord(i)] == 0:
				count[ord(i)] = 1
			else:
				count[ord(i)] += 1
		for i in range(len(count)):
			if count[i] > 0:
				c += chr(i) * count[i]
		return c


class Solution:

	def countSort(self, arr):
		a = sorted(sorted(arr), key=str.upper)
		s = ''
		for i in range(len(a)):
			s = s + a[i]
		return s


class Solution:

	def countSort(self, arr):
		n = len(arr)
		l = [0] * 26
		for i in range(n):
			index = ord(arr[i]) - ord('a')
			l[index] = l[index] + 1
		res = ''
		for i in range(26):
			while l[i] > 0:
				res += chr(i + 97)
				l[i] = l[i] - 1
		return res


class Solution:

	def countSort(self, arr):
		d = {}
		str = ''
		for i in arr:
			if i not in d.keys():
				d[i] = 0
			d[i] += 1
		for i in sorted(d.keys()):
			temp = i * d[i]
			str += temp
		return str


class Solution:

	def countSort(self, arr):
		li = list(arr)
		li.sort()
		st = ''.join(li)
		return st


class Solution:

	def countSort(self, arr):
		ans = ''
		l1 = []
		for i in arr:
			b = ord(i)
			l1.append(b)
		l1.sort()
		for j in l1:
			ans = ans + chr(j)
		return ans


class Solution:

	def countSort(self, arr):
		str1 = ''
		p = sorted(arr)
		for i in p:
			str1 = str1 + i
		return str1


class Solution:

	def countSort(self, arr):
		ind = [0] * 257
		for i in range(len(arr)):
			ind[ord(arr[i])] += 1
		for i in range(1, 257):
			ind[i] += ind[i - 1]
		new_arr = [''] * len(arr)
		for i in range(len(arr)):
			new_arr[ind[ord(arr[i])] - 1] = arr[i]
			ind[ord(arr[i])] -= 1
		return ''.join(new_arr)


class Solution:

	def countSort(self, arr):
		a = sorted(arr, key=lambda x: ord(x))
		s = ''.join(a)
		return s


class Solution:

	def countSort(self, arr):
		arrn = [0] * 26
		for i in range(len(arr)):
			arrn[ord(arr[i]) - ord('a')] += 1
		for j in range(1, len(arrn)):
			arrn[j] = arrn[j] + arrn[j - 1]
		ans = [''] * len(arr)
		for k in range(len(arr)):
			ans[arrn[ord(arr[k]) - ord('a')] - 1] = arr[k]
			arrn[ord(arr[k]) - ord('a')] -= 1
		fans = ''
		for l in ans:
			fans = fans + l
		return fans


class Solution:

	def countSort(self, arr):
		count = [0] * 26
		output = ''
		n = len(arr)
		for i in arr:
			count[ord(i) - 97] += 1
		for i in range(len(count)):
			output += count[i] * chr(i + 97)
		return output


class Solution:

	def countSort(self, arr):
		res = ''.join(sorted(arr))
		return res


class Solution:

	def countSort(self, arr):
		cs = [0] * 26
		s = ''
		for i in arr:
			j = ord(i) - 97
			cs[j] += 1
		for i in range(len(cs)):
			s += cs[i] * chr(i + 97)
		return s


class Solution:

	def countSort(self, arr):
		temp = []
		for i in arr:
			temp.append(i)
		temp.sort()
		return ''.join(temp)


class Solution:

	def countSort(self, arr):
		res = ''
		arr = list(arr)
		arr.sort()
		for i in range(len(arr)):
			res += arr[i]
		return res


class Solution:

	def countSort(self, arr):
		res = ''
		r = sorted(arr)
		for i in range(0, len(r)):
			res += r[i]
		return res


class Solution:

	def countSort(self, arr):
		x = sorted(arr)
		string = ''
		for i in range(len(x)):
			string += x[i]
		return string


class Solution:

	def countSort(self, arr):
		freq_arr = [0] * 26
		ascii_arr = [0] * len(arr)
		for i in range(len(arr)):
			ascii_arr[i] = ord(arr[i])
		for i in ascii_arr:
			freq_arr[i - 97] += 1
		for i in range(1, len(freq_arr)):
			freq_arr[i] = freq_arr[i] + freq_arr[i - 1]
		new_arr = [0] * len(arr)
		for i in range(len(arr) - 1, -1, -1):
			new_arr[freq_arr[ascii_arr[i] - 97] - 1] = ascii_arr[i]
			freq_arr[ascii_arr[i] - 97] -= 1
		for i in range(len(new_arr)):
			new_arr[i] = chr(new_arr[i])
		return ''.join(new_arr)


class Solution:

	def countSort(self, arr):
		x = {}
		alpha = 'abcdefghijklmnopqrstuvwxyz'
		x = {alpha[i]: 0 for i in range(len(alpha))}
		for c in arr:
			if c in x:
				x[c] = x[c] + 1
		res = ''
		for a in alpha:
			count = x[a]
			for i in range(count):
				res = res + a
		return res


class Solution:

	def countSort(self, arr):
		arr = list(arr)
		arr.sort()
		ans = ''
		for i in arr:
			ans += i
		return ans


class Solution:

	def countSort(self, arr):
		N = len(arr)
		x = [0 for i in range(26)]
		ans = ''
		for i in range(N):
			x[ord(arr[i]) - 97] += 1
		for i in range(26):
			for l in range(x[i]):
				ans += chr(i + 97)
		return ans


class Solution:

	def countSort(self, arr):
		s = ''
		a = list(arr)
		p = sorted(a)
		for i in range(len(p)):
			s += p[i]
		return s


class Solution:

	def countSort(self, arr):
		A = [0] * 26
		str = ''
		for item in arr:
			A[ord(item) - ord('a')] += 1
		for j in range(len(A)):
			while A[j] > 0:
				str += chr(j + ord('a'))
				A[j] -= 1
		return str


class Solution:

	def countSort(self, arr):
		count = [0] * 26
		for i in arr:
			idx = ord(i) - ord('a')
			count[idx] += 1
		for i in range(1, len(count)):
			count[i] = count[i - 1] + count[i]
		ans = [0] * len(arr)
		for i in arr:
			idx = ord(i) - ord('a')
			ans[count[idx] - 1] = i
			count[idx] -= 1
		final = ''
		for i in ans:
			final += i
		return final


class Solution:

	def countSort(self, arr):
		store = [0] * 26
		for i in arr:
			store[ord(i) - 97] = store[ord(i) - 97] + 1
		final = ''
		for j in range(len(store)):
			if store[j] != 0:
				final = final + store[j] * chr(j + 97)
		return final


class Solution:

	def countSort(self, s):
		ans = ''
		cnt = dict()
		for x in s:
			if not x in cnt:
				cnt[x] = 0
			cnt[x] += 1
		alphabet = 'abcdefghijklmnopqrstuvwxyz'
		for c in alphabet:
			if c in cnt:
				ans += c * cnt[c]
		return ans