Satya is participating in a treasure hunt - Flipkart Grid

Problem Preview

"Satya is participating in a treasure hunt. The key to the last puzzle is the minimum number of nodes in a "prefix tree" made from a given set of words. She has the flexibility to rearrange the given words in any way possible, to try to minimize the number of nodes. Note that a word's prefix is a subarray of letters that starts from the beginning of the word to a specific point in the word. A prefix tree is a tree like structure that represents all prefixes of words from a certain set in the following way: The root of the tree represents an empty prefix. Each branch of the tree is denoted with a letter from the alphabet. Two branches coming out of a single node (or root) cannot be labeled with the same letter All nodes (except root) in the tree represent a non-empty prefix obtained by concatenating letters of all branches that lead from the root to that node. The puzzle has N words that consist of lowercase letters of the English alphabet. Help Satya by writing a program to find the minimum number of nodes a prefix tree can have after permuting the letters of each word in any manner. Read the input from STDIN and print the output to STDOUT. Do not write arbitrary strings anywhere in the program, as these contribute to the standard output and test cases will fail. Constraints: 1 <= N <= 16 The length of any word will be less than 1,000,000. Input Format: The first line of input contains the integer N. Each of the following N lines contains a single word consisting of lowercase letters of the English alphabet. Output Format: A single line of output contains the minimum number of nodes possible. Sample Input 1: 3 p pq pqr Sample Output 1: 4 Explanation: We can achieve the minimum number of nodes as follows, without having to rearrange any word: (Visual graph showing path: root -> p -> pq -> pqr) Hence the number of minimum nodes needed is 4. Sample Input 2: 5 dajg ddbfjj ddbfii ch c Sample Output 2: 14"