Problem title
Difficulty
Avg time to solve

Ninja and Mathematics
Moderate
30 mins
Minimum Break
Moderate
30 mins
Boyer Moore Algorithm For Pattern Searching
Moderate
30 mins
Distinct Strings With Odd and Even Swapping Allowed
Moderate
15 mins
Split Binary String
Easy
15 mins
Find K-Th Element From Product Array.
Hard
45 mins
Maximize the sum
Moderate
15 mins
Populate Inorder Successor of all nodes of a Binary Tree
Moderate
30 mins
Ninja And Sentences
Moderate
35 mins
Kevin And His Fruits
Moderate
25 mins 2

# Matching Prefix

Difficulty: MEDIUM

Problem Statement

#### Find the string ‘S’ such that the cost of the array ‘Arr’ is minimized. If multiple strings exist, then find the lexicographically smallest string amongst them.

##### For Example :
``````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”.
``````
##### Input Format :
``````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.
``````
##### Output Format :
``````For each test case, print the string which minimizes the cost of the array of deletion of common prefixes.

Output for each test case will be printed in 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 <= 20
1 <= Arr[i].length <= 20

Time limit: 1 sec
``````
##### Sample Input 1 :
``````2
8
co
code
studio
codingninjas
coding
debug
coder
cipher
3
cat
bat
rat
``````
##### Sample Output 1 :
``````cod
bat
``````
##### Explanation For Sample Input 1 :
``````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”.
``````
##### Sample Input 2 :
``````2
1
ninjacoder
2
rabbit
robot
``````
##### Sample Output 2 :
``````ninjacoder
rabbit
``````   Console