Sort Array Of Strings
You are given an array of strings 'ARRSTR[]' of size 'N' and a character 'C'. Your task is to sort the 'ARRSTR[]' according to the new alphabetical order that starts with the given character 'C'.

Note:

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.

Input Format:

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.

Output Format:

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.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1

Question

Sort Array Of Strings

You are given an array of strings 'ARRSTR[]' of size 'N' and a character 'C'. Your task is to sort the 'ARRSTR[]' according to the new alphabetical order that starts with the given character 'C'.

Note:

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.

Input Format:

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.

Output Format:

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.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 1000
'C' is a lowercase English alphabet. 
1 <= | ARRSTR[i] | <= 9, where 1 <= i <= N.

Time Limit: 1sec

Accepted Answer

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

Space Complexity: O(1)Explanation:

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

Time Complexity: O(nlogn)Explanation:

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

Python (3.5)

'''

    Time Complexity: O(N * LogN)

    Space Complexity: O(1),



    where N is the size of the array.

'''



# HashMap for storing the order.

from functools import cmp_to_key

hmap = dict()



# Compare function that return true if string x is to be placed before the string y.

def compare(x, y):

    for i in range(min(len(x), len(y))):

        if x[i] == y[i]:

            # If both character equals, then continue.

            continue

        else:

            # If both character equals, then continue.

            return hmap[x[i]] - hmap[y[i]]



    # If no character differ in the loop then we check for the length.

    return len(x) - len(y)



def sortArrStr(n, arrStr, c):



    # Create a string according to the new alphabetical order.

    newOrder = []

    value = ord(c) - ord('a')



    # Add the character starting from the given character c to z and then a to (c-1).

    for i in range(26):

        newOrder.append(chr(ord('a') + (value + i) % 26))



    # Store the order for each character.

    for i in range(26):

        hmap[newOrder[i]] = i



    # Call the sort function.

    arrStr.sort(key = cmp_to_key(compare))



    return arrStr

Java (SE 1.8)

/*
    Time Complexity: O(N * LogN)
    Space Complexity: O(1),

    where N is the size of the array.
*/

import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
import java.util.Collections;
import java.util.Comparator;

public class Solution {

    public static ArrayList < String > sortArrStr(int n, ArrayList < String > arrStr, char c) {
        
        // HashMap for storing the order.
        Map < Character, Integer > hmap = new HashMap < > ();

        // Create a string according to the new alphabetical order.
        String newOrder = "";
        int value = c - 'a';

        // Add the character starting from the given character c to z and then a to (c-1).
        for (int i = 0; i < 26; i++) {
            newOrder += ((char)((value + i) % 26 + 'a'));
        }

        // Store the order for each character.
        for (int i = 0; i < 26; i++) {
            hmap.put(newOrder.charAt(i), i);
        }

        // Call the sort function.
        Collections.sort(arrStr, new Comparator < String > () {
            @Override
            public int compare(String x, String y) {
                for (int i = 0; i < Math.min(x.length(), y.length()); i++) {
                    if (x.charAt(i) == y.charAt(i)) {
                        continue;
                    } else {
                        return hmap.get(x.charAt(i)) - hmap.get(y.charAt(i));
                    }
                }
                return x.length() - y.length();
            }
        });

        return arrStr;

    }
}

C++ (g++ 5.4)

/*

    Time Complexity: O(N * LogN)

    Space Complexity: O(1),



    where N is the size of the array.

*/



// HashMap for storing the order.

unordered_map < char, int > hmap;



// Compare function that return true if string x is to be placed before the string y.

bool compare(string x, string y) {

    for (int i = 0; i < min(x.length(), y.length()); i++) {



        if (x[i] == y[i]) {

        	// If both character equals, then continue.

            continue;

        }

        else {

        	// Else return true if x is to be placed before y.

            return hmap[x[i]] < hmap[y[i]];

        }



    }



    // If no character differ in the loop then we check for the length.

    return x.length() < y.length();

}



vector < string > sortArrStr(int n, vector < string > & arrStr, char c) {



    // Create a string according to the new alphabetical order.

    string newOrder = "";

    int value = c - 'a';



    // Add the character starting from the given character c to z and then a to (c-1).

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

        newOrder += char((value + i) % 26 + 'a');

    }



    // Store the order for each character.

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

        hmap[newOrder[i]] = i;

    }



    // Call the sort function.

    sort(arrStr.begin(), arrStr.end(), compare);



    return arrStr;

}

You are given an array of strings 'ARRSTR[]' of size 'N' and a character 'C'. Your task is to sort the 'ARRSTR[]' according to the new alphabetical order that starts with the given character 'C'.

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Amadeus Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amadeus Software Developer