Sort String with alternate lower upper.

Easy
0/40
Average time to solve is 15m
profile
Contributed by
4 upvotes
Asked in companies
AmdocsMAQ SoftwareCapegemini Consulting India Private Limited

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1
2
pqrPQR
dBAAa
Sample Output 1
pPqQrR
aAdAB
Explanation of Sample Input 1
Test Case 1: The lowercase letters in the given string ( p,q,r ) and uppercase letters (P, Q, R ) are in sorted order. After arranging them at alternate positions, the resulting string = “pPqQrR”.

Test Case 2: In the given string lowercase letters = d,a and uppercase letters = B,A,A
After sorting and alternate positioning string will become aAdAB. As in this case, we were left with an extra uppercase letter ‘B’, so we have appended it at last.
Sample Input 2
2
bauricn
rdMWcU
Sample Output 2
abcinru
cMdUrW
Hint

Sort uppercase and lowercase letters separately.

Approaches (1)
Brute Force Approach
  • 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’ ].
  • 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’.
Time Complexity

O(|STR|), where |STR| is the length of the string.

 

We are traversing the string once to store every letter’s count and then traversing to place the letters in alternate sorted order. Therefore the overall complexity of both the traversals is O(|STR|).

Space Complexity

O(1).

 

We have used two arrays, ‘upCount’ and ‘lowCount’ of fixed size. So as we have used constant space, the space complexity is O(1).

Code Solution
(100% EXP penalty)
Sort String with alternate lower upper.
Full screen
Console