Given two integers n and k, return a list of all valid binary strings of length n sorted in lexicographical order.

A binary string is considered valid if it satisfies the following conditions:

• It does not contain two consecutive $ ext{‘1’}$ characters.

• The total cost of the string is at most k.

The cost of a binary string is defined as the sum of all $0$ based indices where the character is $ ext{‘1’}$.

Constraints:

• $1 \leq$ n $\leq 12$

• $0 \leq$ k $\leq \frac{ ext{`n`} \cdot ( ext{`n`} - 1)}{2}$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.