PrefixFreeSubsets | Topcoder Archive

Problem Statement

A prefix-free set is a set of words in which no element is a prefix of another element in 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 subsets of words that are prefix-free. Note that both the empty set and the entire set count as subsets.

Definition

Class:: PrefixFreeSubsets
Method:: cantPrefFreeSubsets
Parameters:: String[]
Returns:: long
Method signature:: long cantPrefFreeSubsets(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').
No two elements of words will be equal.

Examples

```
{"hello","hell","hi"}
```
```
Returns: 6
```
There are 23=8 possible subsets. Only the subsets containing both "hello" and "hell" will not be prefix-free. There are 2 of those (one with "hi" and one without), and therefore, there are 8-2=6 prefix-free subsets.
```
{"a","b","c","d"}
```
```
Returns: 16
```
All subsets are prefix-free.
```
{"a","ab","abc","abcd","abcde","abcdef"}
```
```
Returns: 7
```
Only subsets with one or less elements are prefix-free.

{"a","b","aa","ab","ba","bb"}

Returns: 25

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.