Let us assume that all ℓ_{i} are either integers or consist of lowercase English letter only. A label consisting of a mixture of digits and letters cannot be a valid label, and a label that begins with a `0`

cannot be a valid label either. We can cut the sequence before the first such offending label before processing it in the ways described below.

For the easy subtask it was sufficient to try all reasonable possibilities (remember that *k* ≤ 2) and to pick the best one among them.

In other words, we can try the following cases:

- For
*k*= 0 we just generate the sequence of positive integers. - For
*k*= 1 we try all possible 1 ≤*d*_{1}≤*n*, for each of them we check that ℓ_{di}is a 4-character string, and if it is, we generate the corresponding “Fizz sequence”. - For
*k*= 2, once we have a*d*_{1}that was valid for*k*= 1, we also try all*d*_{2}>*d*_{1}and whenever we find one that produces a second valid label, we generate the corresponding Fizz Buzz sequence.

Each time we gerate a sequence, we simply find its longest prefix that matches the input sequence.

The previous solution works but depending on the implementation and programming language used it can already be annoyingly slow. Luckily, there is a simple improvement that will speed up the search significantly.

Suppose we are in the case *k* = 1 and we found the smallest *j* such that the given label ℓ_{j} is a string. Then obviously *d*_{1} = *j* is the only possibility we need to try. Larger *d*_{1} won’t give us a better solution because its sequence will have the number *j* instead of the correct label ℓ_{j} in *j*-th position.

Then, in the case *k* = 2, this *d*_{1} is again the only possible *d*_{1} for the same reason. So instead of *Θ*(*n*^{2}) pairs (*d*_{1}, *d*_{2}) we now only have to try *Θ*(*n*) possible *d*_{2} with this single *d*_{1}.

Instead of applying brute force we will now try to deduce the *d*_{i} and *s*_{i} greedily. This solution will be a fairly straightforward generalization of our better solution for the easy subproblem.

We will go through the given labels from 1 to *n*. At the beginning, there are no pairs (*d*_{j}, *s*_{j}).

Each time we process a new label ℓ_{i}, there are two possibilities:

The label ℓ

_{i}is an integer. In this case we need to check two things. First,*i*must not be a multiple of any of the*d*_{j}we already have. Second, ℓ_{i}must actually be*i*, not some other integer. (Did you miss this on your first try?) If either check fails, we have no way of saving it, this is the end of the valid prefix.The label ℓ

_{i}is a string. In this case we look at the pairs (*d*_{j},*s*_{j}) we already determined, and we use them to construct the (possibly empty) label ℓ_{i}′ we should see according to what we know. Now there are three cases:- If ℓ
_{i}= ℓ_{i}′, everything is in order and we move on. - If ℓ
_{i}′**is not**a proper prefix of ℓ_{i}, there is no way to fix this problem and thus this is the end of a valid prefix. - If ℓ
_{i}′**is**a proper prefix of ℓ_{i}, there is exactly one way to fix this problem: by introducing a new rule with step =*i*and label = the missing part of ℓ_{i}.

- If ℓ

This way we incrementally construct the only possible set of rules that corresponds to the prefix we already processed. Hence, when we get stuck, we can be certain that the solution we just found is optimal.

An alternate implementation of the same idea is that whenever you determine a new rule (*d*_{i}, *s*_{i}), you immediately look at all multiples of *d*_{i}. If the label of a multiple of *d*_{i} starts with *s*_{i}, you remove the prefix *s*_{i} and keep the rest of the label. And if it doesn’t, you cut off the input sequence at that point.