Last Updated: 24 Mar, 2021
Sort String with alternate lower upper.
Easy
Asked in companies
Given a string ‘STR’ containing lowercase and uppercase letters. You need to sort the string so that the resulting string contains uppercase and lowercase letters at alternate positions but in sorted order.
Note
If any lowercase or uppercase letters remains left after alternate positioning, then append them at the last of the string in sorted order.
For Example
If the given string STR = “rDaBfS” then after sorting STR = “aBfDrS”. In the sorted string, lowercase letters a,f,r, and uppercase letters B, D, S are in sorted order and alternate positions.
Input Format
The first line contains ‘T’, denoting the number of test cases.
The first line of each test contains a string 'STR' containing lowercase and uppercase letters.
Output Format
For each test case, print a single line containing a single string denoting the sorted string having the lower case or uppercase letters at alternate positions.
The output for each test case will be printed in a separate line.
Note:
You don't have to print anything. It has already been taken care of. Just implement the given function.
Constraints
1 <= T <= 10
1 <= |STR| <= 10 ^ 5
Where ‘T’ is the number of test cases and |STR| is the string’s length.
Time limit: 1 sec.
Approaches
- We will solve this problem by taking two arrays, ‘upCount’ and ‘lowCount’ of size ‘26’ that will store the count of uppercase and lowercase letters.
- We will traverse the given string and increment its count corresponding to its value.
- Now, ‘upCount’ and ‘lowCount’ will store the count of uppercase and lowercase letters in sorted order, but there will be some characters whose count is ‘0’, i.e., the characters that are not present in the given string.
- We will alternatively pick characters from ‘upCount’ and ‘lowCount’ whose count > 0 and add the character to the resulting string.
Algorithm
- Initialize two 1-D arrays ‘upCount’ and ‘lowCount’ of size 26 with all values ‘0’.
- Iterate the given string - i : 0 to length - 1
- If Str[ i ] is lowercase letter.
- Increment lowCount[ s[ i ] - ‘a’ ].
- Else
- Increment upCount[ s[ i ] - ‘A’ ].
- If Str[ i ] is lowercase letter.
- Take a variable ‘index’, which will store the resulting string index at which the current letter is to be placed.
- Run a loop until index < length of the string.
- Iterate over ‘lowCount’ and get the first letter with count>0.
- If found, place this letter at Str[ index ] and increment ‘index.’
- Iterate over ‘upCount’ and get the first letter with count>0.
- If found, place this letter at Str[ index ] and increment ‘index’.
- Return ‘Str’.