Bundles

The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows. The first line of each test case contains two integers ‘N’ and ‘K’ separated by a single space. ‘N’ denotes the number of strings and ‘K’ denotes the size of each group. The next ‘N’ lines contain a single string.

1 <= T <= 5 1 <= K <= N <= 100 1 <= |STRLIST[i]| <= 1000 “STRLIST[i]” contains only lowercase english letters. Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of strings, ‘K’ denotes the size of each group of the strings, and |STRLIST[i]| denotes the length of the i’th string. Time Limit: 1 sec

In the first test case, both the strings will be in 1 group and they don’t have any common prefix hence the answer is 0. In the second test case, we can form the groups as { “above, “aboard” } and {“tail”, “tower”} , then the first group has a score of 3 and the second group has a score of 1. Hence the total score is 3+1=4.

In the first test case, it is optimal to choose one group as { “am”, “amazing”, “amginza” } and the second group as { “help”, “code”, “give” }. The first group has a score of 2 while the second group has a score of 0. Hence, the total score is 2. In the second test case, we can form the groups as { “hello, “help” } and {“home”, “ninja”}, then the first group has a score of 3 and the second group has a score of 0. Hence the total score is 3.

Brute force Approach

The idea is to store all the prefixes into the HashMap and then calculate the contribution of each prefix in the answer.

Consider a group of strings which has a common prefix of length ‘L’. The score for this group will be ‘L’, we can see that each prefix from 1 to ‘L’ contributes exactly 1 to the final answer. So if any prefix is present in ‘P’ groups then it will contribute exactly ‘P’ to the final answer. The problem is now reduced to finding the individual contribution of each prefix to the final answer.

The steps are as follows :

Declare a HashMap for mapping each prefix to the number of times it occurs. The key of the HashMap will be a string and it’s value will be an integer that denotes the occurrence of the key.
Iterate through the given strings
1. For each prefix of the current string, increment the value in the HashMap by 1 corresponding to the prefix as the key.
Declare a variable “finalScore” and initialize it to 0. We will use this variable to store the sum of scores of each group.
Now iterate through the HashMap, let’s say the value of the current key is “count”.
1. The contribution of the current key will be floor(count/K) because we need K strings with a common prefix to form one group.
2. Add floor(count/k) to “finalScore”.
Return “finalScore” as this will be the maximum sum of scores of all groups.

Time Complexity

O(N * max(|S|) ^ 2), where ‘N’ is the number of strings and max(|S|) is the maximum length of the given strings.

We are inserting each prefix of all the strings into the HashMap. There are ‘N’ strings and each string can be of the length of (max|S|). There will be max(|S|) prefixes in the string and calculating each prefix will take O(max(|S|)) time on average. Also, search and insert operations in the HashMap will take time equal to the length of the string. Thus, the total time complexity will be O(N * |S| ^ 2).

Space Complexity

O(N * max(|S|)), where ‘N’ is the number of strings and max(|S|) is the maximum length of the given strings.

We are inserting each prefix of all the strings into the HashMap. There are ‘N’ strings and each string can be of length (max|S|). There will be max(|S|) prefixes in the string. Thus there will be a total of N * (max(|S|)) prefixes in the HashMap. Thus, the overall space complexity will be O(N * max(|S|)).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation of Sample Input 1 :

Sample Input 2 :

Sample Output 2 :

Explanation of Sample Input 2 :