PrefixFreeSets | Topcoder Archive

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

```
{"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.

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)2024, Topcoder, Inc. All rights reserved.