Sort String with alternate lower upper.
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

Question

Sort String with alternate lower upper.

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.

Accepted Answer

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’.

Space Complexity: O(1)Explanation:

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).

Time Complexity: OtherExplanation:

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|).

Python (3.5)

"""

    Time Complexity : O( |STR| )

    Space Complexity : O( 1 )

    

    where |STR| is the length of the string.



"""



# Converts string to list.

def Convert(string):

    list1 = []

    list1[:0] = string

    return list1





def sortString(s):



    # Initializing 1-D array to keep count of lowercase and uppercse letters.

    upCount = [0]*26

    lowCount = [0]*26



    # Iterating over the string to keep count of letters.

    for i in range(len(s)):



        if (ord(s[i]) >= 97 and ord(s[i]) <= 122):

            lowCount[ord(s[i]) - ord('a')] += 1

        else:

            upCount[ord(s[i]) - ord('A')] += 1



    index = 0



    # Filling letters in string with alternate lowercase and uppercase letters.

    s = Convert(s)

    while (index < len(s)):



        for i in range(26):



            if (lowCount[i] > 0):



                s[index] = chr(ord('a') + i)

                index += 1

                lowCount[i] -= 1

                break



        for i in range(26):



            if (upCount[i] > 0):



                s[index] = chr(ord('A') + i)

                index += 1

                upCount[i] -= 1

                break

            

    # Converting list back to string.       

    return ''.join(s)

C++ (g++ 5.4)

/*

    Time Complexity : O( |STR| )

    Space Complexity : O( 1 )



    where |STR| is the length of the string.



*/



#include 



string sortString(string &str)

{

	

    int upCount[26] = {0};

    int lowCount[26] = {0};

    

    // Iterating over the string to keep count of letters.

    for (int i = 0; i < str.length(); i++)

    {

        if (str[i] >= 97 && str[i] <= 122)

            lowCount[str[i] - 'a']++;

        else

            upCount[str[i] - 'A']++;

    }



    int index = 0;

	

	// Filling letters in string with alternate lowercase and uppercase letters.

    while (index < str.length())

    {

        for (int i = 0; i < 26; i++)

        {

            if (lowCount[i] > 0)

            {

                str[index] = 'a' + i;

                index++;

                lowCount[i]--;

                break;

            }

        }

        for (int i = 0; i < 26; i++)

        {

            if (upCount[i] > 0)

            {

                str[index] = 'A' + i;

                index++;

                upCount[i]--;

                break;

            }

        }

    }



    return str;

}

Java (SE 1.8)

/*

    Time Complexity : O( |STR| )

    Space Complexity : O( 1 )



    where |STR| is the length of the string.



*/



public class Solution {

    public static String sortString(String str) {



        int upCount[] = new int[26];

        int lowCount[] = new int[26];

        char[] Str = str.toCharArray();



        // Iterating over the string to keep count of letters.

        for (int i = 0; i < str.length(); i++) {



            if (Str[i] >= 97 && Str[i] <= 122) {

                lowCount[Str[i] - 'a']++;

			}

            else {

                upCount[Str[i] - 'A']++;

			}

        }



        int index = 0;



        // Filling letters in string with alternate lowercase and uppercase letters.

        while (index < str.length()) {



            for (int i = 0; i < 26; i++) {

                if (lowCount[i] > 0) {

                    Str[index] = (char)('a' + i);

                    index++;

                    lowCount[i]--;

                    break;

                }

            }



            for (int i = 0; i < 26; i++) {

                if (upCount[i] > 0) {

                    Str[index] = (char)('A' + i);

                    index++;

                    upCount[i]--;

                    break;

                }

            }

        }



        return String.valueOf(Str);



    }

}