| A codeset is a set of n binary strings (the codes) that could be used to
encode messages based on an alphabet of size n. In order to be able to
decode the result, a codeset must have the property that no code is a prefix
of any other code. A codeset is "maximal" if it is not possible to add
any additional code to the codeset without violating the prefix requirement.
We are interested in how many different codesets of size n exist. For example,
when n=4 there are 5 different maximal codesets:
{"000","001","01","1"}, {"010","011","00","1"}, {"111","110","10","0"},
{"101","100","11","0"}, {"00","11","01","10"}
Oh yes, we have a favorite code and we are only interested in codesets that
include that code.
You are given n, the size of each codeset, and a binary String favorite. Return the number of maximal codesets of size n that contain favorite. If there are more than 1,000,000,000, return -1 instead.
|