Matching Prefix
You are given an integer ’N’ denoting the length of the array ‘Arr’ of strings made up of lower case English alphabets. The cost of this array is equal to the sum of length of each string in the array.

You can select a new string ‘S’ of length ‘N’, you are now allowed to delete the prefix from the strings in the array (This leads to lowering the cost of the array), the deleted prefix should be exactly the same as the selected string ‘S.

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

Question

Matching Prefix

You are given an integer ’N’ denoting the length of the array ‘Arr’ of strings made up of lower case English alphabets. The cost of this array is equal to the sum of length of each string in the array.

You can select a new string ‘S’ of length ‘N’, you are now allowed to delete the prefix from the strings in the array (This leads to lowering the cost of the array), the deleted prefix should be exactly the same as the selected string ‘S.

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O( 1 )

No extra space is used.

Hence the space complexity is O(1).

Time Complexity: OtherExplanation:

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)).

Python (3.5)

'''

Time Complexity: O(N ^ 2 * L ^ 2)

Space Complexity: O(1)



where  N and L denotes the number of strings and the maximum length of string respectively

'''



INT_MAX = 10000000000





def matchingPrefix(N, arr):

    # Initialize minCost to store minimum cost

    minCost = INT_MAX



    # Initialize ans to store the string to be returned

    ans = ""



    # iterate each string

    for i in range(N):



        # Iterating each charachter of the string

        for j in range(len(arr[i])):



            # Variable to store the the current cost

            curCost = 0



            # Variable to store current length of prefix string

            ln = j + 1



            # Current prefix string

            prefixStr = arr[i][0:ln]



            # Iterate each string

            for k in range(N):

                # Increment current cost with length of string

                curCost += len(arr[k])

                # Checking if the size of string is atleast 'len'

                if len(arr[k]) >= ln:

                    newStr = arr[k][0:ln]



                    if newStr == prefixStr:

                        # Matching prefix string found

                        curCost -= ln



            # Updating the answer if a lower cost is found

            if (curCost < minCost):

                minCost = curCost

                ans = prefixStr



            # Updating the answer if a lexicographically smaller string is found

            if (curCost == minCost):

                if ans > prefixStr:

                    ans = prefixStr



    return ans

Java (SE 1.8)

/*

    Time Complexity: O( N^2 * L^2 )

    Space Complexity: O(1)



    where  N and L denotes the number of strings and the maximum length of string respectively

*/



import java.util.ArrayList;

public class Solution {

    public static String matchingPrefix(int N, ArrayList < String > arr) {

        

        // Initialize minCost to store minimum cost

        int minCost = Integer.MAX_VALUE;



        // Initialize ans to store the string to be returned

        String ans = new String();



        // Iterate each string

        for (int i = 0; i < N; i++) {



            // Iterating each charachter of the string

            for (int j = 0; j < arr.get(i).length(); j++) {



                // Variable to store the the current cost

                int curCost = 0;



                // Variable to store current length of prefix string

                int len = j + 1;



                // Current prefix string 

                String prefixStr = arr.get(i).substring(0, len);



                // Iterate each string

                for (int k = 0; k < N; k++) {



                    // Increment current cost with length of string

                    curCost += arr.get(k).length();



                    // Checking if the size of string is atleast 'len'

                    if (arr.get(k).length() >= len) {



                        // New prefix string of length equal to 'len'

                        String newStr = arr.get(k).substring(0, len);



                        if (newStr.equals(prefixStr)) {



                            // Matching prefix string found

                            curCost -= len;



                        }

                    }

                }



                // Updating the answer if a lower cost is found

                if (curCost < minCost) {

                    minCost = curCost;

                    ans = prefixStr;

                }



                // Updating the answer if a lexicographically smaller string is found

                if (curCost == minCost) {

                    if (ans.compareTo(prefixStr) > 0) ans = prefixStr;

                }



            }

        }



        return ans;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O( N^2 * L^2 )

    Space Complexity: O(1)



    where  N and L denotes the number of strings and the maximum length of string respectively

*/



string matchingPrefix(int n, vector < string > arr) {



   // Initialize minCost to store minimum cost

   int minCost = INT_MAX;



   // Initialize ans to store the string to be returned

   string ans;



   // Iterate each string

   for (int i = 0; i < n; i++) {



      // Iterating each charachter of the string

      for (int j = 0; j < arr[i].size(); j++) {



         // Variable to store the the current cost

         int curCost = 0;



         // Variable to store current length of prefix string

         int len = j + 1;



         // Current prefix string 

         string prefixStr = arr[i].substr(0, len);



         // Iterate each string

         for (int k = 0; k < n; k++) {



            // Increment current cost with length of string

            curCost += arr[k].size();



            // Checking if the size of string is atleast 'len'

            if (arr[k].size() >= len) {



               // New prefix string of length equal to 'len'

               string newStr = arr[k].substr(0, len);



               if (newStr == prefixStr) {



                  // Matching prefix string found

                  curCost -= len;



               }

            }

         }



         // Updating the answer if a lower cost is found

         if (curCost < minCost) {

            minCost = curCost;

            ans = prefixStr;

         }



         // Updating the answer if a lexicographically smaller string is found

         if (curCost == minCost) {

            if (ans > prefixStr) ans = prefixStr;

         }



      }

   }



   return ans;

}

Accepted Answer

Hash-map

For each string in the array consider each of its prefix strings one by one and increment frequency associated with it in the hash-map.

Also pre-compute the original cost of the given array of strings, this cost is equal to the sum of the length of each string.

In the end, simply iterate the hash-map, for each prefix string if we use it then cost will be reduced by the length of the prefix string multiplied by its frequency from the original cost.

Find the optimal answer and return it.

The steps are as follows :

Initialize cost to store the cost of the original array of strings given as input.
Initialize a hash-map mp to store the frequency of each prefix string.
Iterate each string of the array one by one, and generate all prefixes for each string and increment frequency corresponding to it in mp.
Initialize minCost to INT_MAX it will store the minimum cost so far, and initialize ans to store the string to be returned.
Iterate the hash-map, use the curCost to store the cost if the current prefix string is used. curCost is equal to cost - ( curPrefix.length * freq[ curPrefix ] )
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.

Space Complexity: OtherExplanation:

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. We store each of them in a hash map.

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