TopCoder problem "PrefixFreeSets" used in SRM 313 (Division I Level One , Division II Level Two)



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 String[] 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:String[]
Returns:int
Method signature:int maxElements(String[] words)
(be sure your method is public)
    
 

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.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6569

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9993&pm=6569

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , legakis , Olexiy

Problem categories:

Simulation