String Sort

Moderate

0/80

Average time to solve is 30m

Contributed by

7 upvotes

Problem statement

You are given ‘N’ strings, and you would like to sort them in lexicographical order (A string 'S' is lexicographically ordered before 'T' if 'S' occurs before 'T' in the English dictionary i.e alphabetical ordering).

However, you cannot swap or change the positions of any strings. The only operation you can do is reverse some of the strings. Each string has a cost associated with it, and reversing a string ‘Str[i]’ costs ‘Cost[i]’ rupees.

Calculate the minimum cost required to make all the strings lexicographically ordered, or report that it is impossible by printing -1.

For example :

 If the strings are [‘ba’, ‘ac’] and the cost array is [3,2], reversing the second string costs ‘2’ rupees and sorts the strings. It can be proved that this is the least possible cost that can be achieved.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains 'T', denoting the number of test cases.

For each Test :

The first line contains an integer ‘N’, the size of the array.
The second line contains ‘N’ space-separated integers, denoting the ‘Cost’ array.
The next ‘N’ lines each contain a string, Str[i].

Output Format :

For each test case, print the minimum cost required to sort the strings or ‘-1’ if it is impossible to sort them. Print the answer for each case on a new line.

Note :

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 10
2 <= N <= 10^5
0 <= Cost[i] <= 10^4
1 <= Size(Str[i]) <= 10^5

Note: It is guaranteed that the sum of N across all test cases will be at most 10^5, and the sum of sizes of the strings across all cases is also 10^5. All strings only contain lowercase English alphabets.

Time Limit: 1 sec

Sample Input 1 :

1
3
2 3 1
ba
ac
zzz

Sample Output 1 :

Explanation for Sample Input 1 :

For test case 1 :
    Reversing the first string costs 2, and makes the strings sorted.

Sample Input 2 :

Sample Output 2 :

-1

Approaches (1)

Approach 1

Dynamic Programming

Time Complexity

Space Complexity

(100% EXP penalty)

String Sort

Console