Round A 2020 Google Kick Start Bundling Problem | JAVA | Know About

Problem

Pip has N strings. Each string consists only of letters from A to Z. Pip would like to bundle their strings into groups of size K. Each string must belong to exactly one group.

The score of a group is equal to the length of the longest prefix shared by all the strings in that group. For example:


The group {RAINBOW, RANK, RANDOM, RANK} has a score of 2 (the longest prefix is 'RA').

The group {FIRE, FIREBALL, FIREFIGHTER} has a score of 4 (the longest prefix is 'FIRE').

The group {ALLOCATION, PLATE, WORKOUT, BUNDLING} has a score of 0 (the longest prefix is '').


Please help Pip bundle their strings into groups of size K, such that the sum of scores of the groups is maximized.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the two integers N and K. Then, N lines follow, each containing one of Pip's strings.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum sum of scores possible.

Sample #1
In Case #1, Pip can achieve a total score of 0 by make the groups:

{KICK, START}, with a score of 0.
In Case #2, Pip can achieve a total score of 10 by make the groups:


{G, G}, with a score of 1.
{GO, GO}, with a score of 2.
{GOO, GOO}, with a score of 3.
{GOOO, GOOO}, with a score of 4.
Sample #2
In Case #1, Pip can achieve a total score of 6 by make the groups:


{RAINBOW, RANK, RANDOM}, with a score of 2.
{FIREBALL, FIREWALL, FIREFIGHTER}, with a score of 4.


PROGRAM


import java.io.*; import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in))); int n,k; int t=sc.nextInt(); for(int i=0;i<t;i++) { n=sc.nextInt(); k=sc.nextInt(); String[] a = new String[n]; for(int j=0;j<n;j++) { a[j]=sc.next(); } System.out.printf("Case #%d: %s\n",i+1,max(a,k)); } } private static Object max(String[] a, int k) { TrieNode root = new TrieNode(); for (String word : a){ root.insert(word); } return root.count(k); } private static class TrieNode { private final TrieNode[] child; private char cont; private int count; public TrieNode() { count=0; child = new TrieNode[26]; } public TrieNode(char cont) { this(); } public void insert(String word) { insert(word.toCharArray(),0); } private void insert(char[] charArray, int i) { if (charArray.length == i) return; char letter = charArray[i]; if (child[letter - 'A'] == null) { child[letter - 'A'] = new TrieNode(letter); } child[letter - 'A'].count++; child[letter - 'A'].insert(charArray, i + 1); } public int count(int k) { int counter = this.count / k; for (int i = 0; i < 26; i++){ if (child[i] != null){ counter += child[i].count(k); } } return counter; } } }

Here is the link for Google KickStart Round A 2020 Allocation problem using JAVA.