Party Over

The first line of input contains an integer ‘T,’ denoting the number of test cases. The test cases follow. The first line of each test case contains a number ‘n’ denoting the number of strings. The second line of each test case contains ‘n’ space-separated strings that the monster gave to Ninja.

In the first test case, the given strings are [“abc”,”abd”,”xyb”,”cdg”], the last character of strings are: ‘c’,’d’,’a’,’b’,’g’. So their sorted order is: ‘a’,’b’,’c’,’d’,’g’. Hence the sorted order of strings are:“aba”,”xyb”,”abc”,”abd”,”cdg”. In the second test case, the given strings are [“jog”,”nop”,”oop”] the last characters of strings are: ‘g’,’p’,’p’.So their sorted order is : ‘g’,’p’,’p’. As we can see for strings “oop” and “nop”, their last character matches; we need to check from the second previous character till we find a mismatched character and sort them accordingly. Hence the sorted order of strings are: “jog”,” nop”,” oop”.

In the first test case, the given strings are [“truck”,”bus”,”car”,”auto”], the last character of strings are: ‘k’,’s’,’r’,’o’.So their sorted order is: ‘k’,’o’,’r’,’s’’. Hence the sorted order of strings are:“truck”,”auto”,”car”,”bus”. In the second test case, the given strings are [“teacher”,”student”,”headmaster”] the last characters of strings are: ‘r’,’t’,’r’.So their sorted order is : ‘r’,’r’,’t’. As we can see for strings “teacher” and “headmaster”, their last character matches; we need to check from the second previous character till we find a mismatched character and sort them accordingly. Hence the sorted order of strings are: “teacher”,” headmaster”,”student”.

Brute Force

The idea is to reverse all the strings and then sort them in alphabetical order and return the sorted strings back in their original form. We can use a nested loop and compare each string with all the preceding strings to sort the strings.

The steps are as follows:

Initially, input a string array “arr” containing all the strings needed to be sorted based on the last character.
Reverse the array containing all the strings using the in-built reverse() function.
We will apply a nested loop with the outer loop pointed by ‘i’ starting from 0 and going till ‘n’ - 1 where ‘n’ is the number of strings in the array and the inner loop pointed by j=i+1 and going till ‘n.’
Now we will start comparing the strings arr[i] and arr[j] using the relational operators.
We will check if the compare() function returns a value greater than 0. If it does, then we can be sure that arr[i] is lexicographically more significant than the string arr[j].
Hence swap both strings using the in-built swap function.
After the swapping operation is performed, reverse back all the strings in their original form.
We will return the array containing all the strings as the answer.

Time Complexity

O((N*K)^2), where N is the number of strings and K is the maximum length of the strings.

Initially, we reverse the strings which will take O(N) time, after which we iterate using two nested loops and compare each string with the preceding string. In the worst case, all the strings could be the same, so we need to traverse the complete array which will take additional O(K) time. After the swapping operation is performed, reverse back all the strings which again takes O(N) time. Hence, the overall time complexity is O(N)+O((N*K)^2)+O(N) = O((N*K)^2)

Space Complexity

O(1), no extra space required.

As we are not using any extra space. Hence, the overall 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: