String Sort

Easy

0/40

Contributed by

17 upvotes

Asked in companies

Problem statement

You are given a string ‘S’ consisting of lowercase English alphabets from ‘a’ to ‘z’. You have to print the string in sorted order.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains a string ‘S’ denoting a string.

Example :

S = ‘bbccdefbbaa’

We sort the string lexicographically or in dictionary order.

Output is: ‘aabbbbccdef’.

Output format :

For each test case, output the sorted string.

Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10 
1 <= S.length <= 10^5
‘a’ <= S[i] <= ‘z’

Time Limit: 1 sec

Sample Input 1 :

2
kbfhh
jjkiia

Sample Output 1 :

bfhhk
aiijjk

Explanation Of Sample Input 1 :

For test case 1 we have, 

The sorted string in lexicographical order is: bfhhk

For test case 2 we have,

The sorted string in lexicographical order is: aiijjk

Sample Input 2 :

2
dbahff
ccbbj

Sample Output 2 :

abdffh
bbccj

Approaches (2)

Approach 1

Approach 2

Inbuilt Function

Use Inbuilt sort function.

Time Complexity

O( N * log( N ) ), where ‘N’ is the length of the string.

The inbuilt sort function takes ~N * log ( N ) for sorting.

Hence the overall time complexity is O( N * log( N ) ).

Space Complexity

O( 1 ), where ‘N’ is the length of the string.

Merge operation takes ~N space.

Hence, the overall Space Complexity is O( 1 ).

(100% EXP penalty)

String Sort

Console