Matching Prefix

If the array of strings is: {co, code, studio, codingninjas, coding, debug, coder, cipher} Then the original cost of the array is 2 + 4 + 6 + 12 + 6 + 5 + 5 + 6 = 46. If we select the new string as “cod” and delete the matching prefixes if exists then the array becomes: {co, e, studio, ingninjas, ing, debug, er, cipher}, and the cost now becomes: 2 + 1 + 6 + 9 + 3 + 5 + 2 + 6 = 34. You can check for any other possible string, the cost will not become less than 34, hence the optimal answer for this case is “cod”.

The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows: The first line of each test case contains a single integer ‘N’ denoting the length of the array of strings. The next N lines each contain ‘Arr[i]’ consisting of lower case English alphabets, denoting the ith string in the array.

For test case 1 : If we choose a string as “cod” and delete the matching prefixes from the array of strings, then the array becomes: {“co”, “e”, “studio”, “ingninjas”, “ing”, “debug”, “er”, “cipher”}. Cost of this array is: 2 + 1 + 6 + 9 + 3 + 5 + 2 + 6 = 34, this is the lowest possible cost we can get. For test case 2 : If we choose a string as “bat” and delete the matching prefixes from the array of strings, then the array becomes: { “cat”, “”, “rat” }, the cost of this array is 3 + 0 + 3 = 6. If we choose “cat” or “rat” then also we will have the cost equal to 6, but we need to return the lexicographically shortest string if multiple outputs are possible, hence we return “bat”.

Brute Force

For each string in the array consider each of its prefix string one by one, now check what will be the cost if the current prefix string is used to delete matching prefixes from all the strings in the array. Keep track of the prefix string that had the lowest cost and finally return that string.

The steps are as follows :

Initialize minCost to INT_MAX it will store the minimum cost so far, and initialize ans to store the string to be returned.
Iterate each string of the array one by one, and generate all prefixes for each string.
Initialize curCost equal to 0, curCost will store the cost if the prefix currently generated is used as our answer.
To calculate curCost, iterate the strings in the array and add the length of each string to curCost.
While iterating each string, if the string length is greater than equal to the length of the current prefix string, check if prefix of the string is equal to the current prefix string, decrement value equal to the length of the current prefix string from curCost if this is true.
After checking all the strings, if curCost calculated is less than minCost then update minCost and ans, if curCost is equal to minCost then update ans if current prefix string is lexicographically smaller.
Finally, return the string stored in ans.

Time Complexity

O( N² * L² ), where N and L denotes the number of strings and the maximum length of string respectively

We generate each prefix string of all the N strings in the array, there are be ~(N*L) prefix strings. Now for each prefix string generated, we try matching it with each of the N strings in the array, the matching operation takes time equal to the length of the string being matched.

Hence the time complexity is O((N*L)*(N*L)).

Space Complexity

O( 1 )

No extra space is used.

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 :