PrefixFreeSets
SRM 313 · 2006-07-26 · by soul-net
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
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').
{"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".
{"a","b","cba","cbc","cbb","ccc"}
Returns: 6
This set is already prefix-free, so the best subset is itself, with 6 elements.
{"a","ab","abc","abcd","abcde","abcdef"}
Returns: 1
Any pair of words is forbidden, so the best subset has only 1 element.
{"topcoder","topcoder","topcoding"}
Returns: 2
"topcoder" is a prefix of "topcoder", so we can only have one of them in the subset.
{"a"}
Returns: 1
Submissions are judged against all 132 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PrefixFreeSets with a public method int maxElements(vector<string> words) · 132 test cases · 2 s / 256 MB per case