Sort Array Of Strings

1) The character ‘C’ is a lowercase English alphabet that is given as input. 2) For example, if the character is 'C' is "d" then, the alphabetical order starts with "d" will look like {d,e,f,....,y,z,a,b,c}. 3) Every string in the array consists of only lowercase English alphabets.

The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then, the 'T' test cases follow. The first line of each test case contains a positive integer 'N' denoting the size of the array and a character 'C', as described in the problem statement. The second line of each test case contains a sequence of 'N' space-separated strings denoting the elements of the array.

For each test case, print in a new line a sequence of 'N' space-separated strings after sorting according to the new alphabetical order given in the problem. Output for each test case will be printed in a separate line.

In the first test case, the new alphabetical order that starts with "h" is “hijklmnopqrstuvwxyzabcdefg”. So, the order of the characters ‘p’, ‘a’, ‘m’, ‘o’ in the new alphabetical order is ‘m’ → ‘o’ → ‘p’ → ‘a’. Hence, the answer is “my offer please accept”.

In the first test case, according to the new alphabetical order, ‘c’ comes first, then ‘n’, so coding comes ahead of ninjas. In the second test case, according to the new alphabetical order, ‘z’ comes first. As there is only one word so there would be no change in sentence.

HashMap Approach

Approach: The idea here is to use a data structure HashMap to store each character’s order in the new alphabetical order, starting with a letter c (given in the problem). Now, start comparing the strings in the ‘ARRSTR[]’ using HashMap that has been created to define the order.

Suppose that we are comparing two strings of ‘ARRSTR[]’ named ‘X’ and ‘Y’. Let us assume that we have found the first different character at the ith index, so if the order (already stored in the HashMap) of ‘X[i]’ is less than the ‘Y[i]’, then ‘X’ is to placed in the front of ‘Y’ (not necessarily adjacent to ‘Y’), and vice-versa.

Algorithm is as follows:

Create a string consisting of the new alphabetical order named as ‘NEWORDER’. So, ‘NEWORDER’ must contain all the characters starting from character ‘C’ to ‘z’, and then ‘a’ to the character just before 'C'. For example, if the character ‘C’ is ‘d’, then, ‘NEWORDER’ = “defghijklmnopqrstuvwxyzabc”.
Create a HashMap named as ‘HMAP’ to store the order.
Run a loop to iterate through the ‘NEWORDER’ with the help of variable ‘i’:
- Make ‘HMAP[NEWORDER[i]]’ = ‘i’.
Now define a custom comparator function named ‘COMPARE’ to sort the strings according to the new alphabetical order.
Sort the strings with the help of ‘COMPARE’.
Return the array of strings ‘ARRSTR’.

bool compare(string x, string y) :

This function is used to sort the strings in the order already defined in the HashMap.
Run a loop with the variable ‘i’ = 0 to min('X.length()' , ‘Y.length()’) :
- If the ith character of both the strings is the same, then just continue.
- Else, return ‘HMAP[X[i]]’ < ‘HMAP[Y[i]]’.
If the loop completes then, return ‘X.length()’ < ‘Y.length()’ (because all the characters are the same, so the smaller string should be placed before the larger one in terms of length).

Time Complexity

O(N*logN), where N is the size of the array.

We are sorting the array of strings of length N, which takes O(N log N) time. Since the length of each string <= 9, we neglect this while calculating the time complexity. Hence, the overall time complexity is O(N log N).

Space Complexity

O(1).

We are using a string newOrder and a hashmap. Both are of size 26 only, which is independent of the size of the input. Hence, the space complexity is O(1).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation for sample input 1:

Sample Input 2:

Sample Output 2:

Explanation for sample input 2: