Sort The Strings

Moderate

0/80

Contributed by

72 upvotes

Problem statement

Ninja has an array, ‘S’, of ‘N’ words, each word consisting of lowercase English letters. An array of words is good if they are in lexicographical order. Ninja would like to make the array ‘S’ good. However, the only move Ninja can perform is to reverse any number of them as many times as he wants.

Let ‘A[i]’ be the cost to reverse the word ‘S[i]’. Let ‘C’ be the minimum total cost to make the array ‘S’ good. Calculate the value of ‘C’. If it’s impossible to make the array good, return the integer ‘-1’.

Example :

N = 3, A = [ 4, 8, 6 ], S = [ “tb”, “ay”, “yb” ]
For each string, we have 2 choices, whether to reverse it or not.
For [ “tb”, “ay”, “yb”], not sorted in lexicographical order.
For [ “tb”, “ay”, “by”], not sorted in lexicographical order.
For [ “tb”, “ya”, “yb”], sorted in lexicographical order and the cost is 0 + 8 + 0 = 8.
For [ “tb”, “ya”, “by”], not sorted in lexicographical order.
For [ “bt”, “ay”, “yb”], not sorted in lexicographical order.
For [ “bt”, “ay”, “by”], not sorted in lexicographical order.
For [ “bt”, “ya”, “yb”], sorted in lexicographical order and the cost is 4 + 8 + 0 = 12.
For [ “bt”, “ya”, “by”], not sorted in lexicographical order.
Hence, the answer is 8.

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

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases, then the test case follows.

The first line of each test case contains a single integer, ‘N’, denoting the number of strings.

The second line contains ‘N’ space-separated integers denoting the elements of the cost array ‘A’.

The next ‘N’ lines contain the array ‘S’ elements, a single string containing lowercase English letters per line.

Output Format :

For each test case, calculate the minimum total cost to make the array ‘S’ good. Return the integer ‘-1’ if it’s impossible.

Output for each test case will be printed on a separate line.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
0 ≤ A[i] ≤ 10^4
1 ≤ ∑ len(S[i]) ≤ 10^6

Time limit: 1 sec

Sample Input 1 :

2
4
4 1 1 5
txmt
gyzw
rsvp
dhyj
6
5 4 4 2 3 5
sla
brog
hqt
qsp
lqhw
may

Sample Output 1 :

-1
13

Explanation For Sample Input 1 :

For test case 1:
We will print -1 because there is no way to make the array good.

For test case 2:
One possible arrangement is [ “als”, “brog”, “hqt”, “qsp”, “whql”, “yam” ], i.e., reverse the string numbers 1, 5, and 6th, then the cost is 5 + 3 + 5 = 13, which is the minimum cost possible.

Sample Input 2 :

2
4
5 1 5 2
wivig
lq
xjp
ep
5
3 5 5 3 5
azyjd
fm
pm
vnwwl
hryx

Sample Output 2 :

-1
5

Explanation For Sample Input 2 :

For test case 1:
We will print -1 because there is no way to make the array good.

For test case 2:
We can reverse the last string with a cost of 5. It can be proved that this is the minimum possible cost. Hence, we will print 5.

Hint 1

For the i-th string, it only needs to be checked with ‘i-1’-th string assuming the strings are sorted till ‘i-1’-th string.

Approaches (1)

Approach 1

Dynamic Programming

Approach:
• Consider a string at position ‘i’. Let dp[i][0] be the minimum amount to sort the strings till position ‘i’ without reversing the i-th string and dp[i][1] be the minimum amount to sort the strings till position ‘i’ and reversing the i-th string.
• We have dp[i-1][0] and the dp[i-1][1], the minimum amount to sort the strings till 'i-1'-th position by reversing or not reversing the 'i-1'-th string
• Now, the string at position ‘i’ needs to be lexographically greater than the string at position ‘i-1’.
• The previous string may or may not have been reversed.
• So, we calculate the answer for both.
• The current string may or may not have to be reversed.
• Again we will calculate the answer for both.
• So, we will check for all these ways and calculate the answer for dp[i][0] and dp[i][1].
• The final answer will be the minimum of dp[n][0] and dp[n][1].

Time Complexity

We only traverse the array of strings once, hence the time complexity will be O(n).

Space Complexity

We create a dp table of size N*2, hence the space complexity will be O(n).

(100% EXP penalty)

Sort The Strings

Console