Minimum Trie Nodes After Reordering Letters

You are given a list of lowercase strings words. You may reorder the letters inside each string however you like, and you choose the order for each string on its own.

The strings are then stored together in a prefix tree. A prefix tree is a rooted tree. Its root stands for the empty string, and every other node carries one letter, so each node spells out the string formed by the letters from the root down to that node.

Storing a string means walking the path that spells it and creating any node on that path that is missing. Two strings therefore share nodes for as long as their letters agree, and use separate nodes from the first position where they differ.

Return the smallest number of nodes the prefix tree can have, counting the root.

Examples

Example 1

Input: words = ["pqr","qps","ptr"]
Output: 7
Explanation: Reorder the second string to "pqs", which lets it share p and q with the first string. Below the root sits p, below p sit q and t, below q sit r and s, and below t sits r. With the root that is 7 nodes.

Example 2

Input: words = ["abc","cba"]
Output: 4
Explanation: Reorder the second string to "abc". Both strings then follow the same path of three nodes below the root.

Example 3

Input: words = ["ab","cd"]
Output: 5
Explanation: The two strings share no letter, so no reordering lets them share a node. The tree holds the root plus two nodes for each string.