PROBLEM STATEMENT
A prefix-free set is a set of words such that no element in the set is a prefix of another element
of the set. For example {"hello"} , {"hello", "goodbye", "giant", "hi"} and the empty set are
examples of prefix-free sets. On the other hand, {"hello","hell"} and {"great","gig","g"} are not
prefix-free.
You will be given a vector words containing a set of words, and you must return the
number of elements in the largest prefix-free subset of words.
DEFINITION
Class:PrefixFreeSets
Method:maxElements
Parameters:vector
Returns:int
Method signature:int maxElements(vector words)
NOTES
-A prefix of a string is the result of erasing zero or more characters from the right end of that
string.
CONSTRAINTS
-words will contain between 1 and 50 elements, inclusive.
-Each element of words will contain between 1 and 50 characters, inclusive.
-Each character of each element of words will be a lowercase letter ('a'-'z').
EXAMPLES
0)
{"hello","hi","h","run","rerun","running"}
Returns: 4
{"hello","hi","run","rerun"} is a possible subset with 4 elements. Each subset having at least 5
elements will always contain one of these forbidden pairs: "run" and "running", or "h" and "hi".
1)
{"a","b","cba","cbc","cbb","ccc"}
Returns: 6
This set is already prefix-free, so the best subset is itself, with 6 elements.
2)
{"a","ab","abc","abcd","abcde","abcdef"}
Returns: 1
Any pair of words is forbidden, so the best subset has only 1 element.
3)
{"topcoder","topcoder","topcoding"}
Returns: 2
"topcoder" is a prefix of "topcoder", so we can only have one of them in the subset.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.