1055. Choice Iterator

Medium3.5 points estimatedDesignIteratorBacktrackingString3 hints
RPby Rohit Parihar

A quiz generator must offer every possible answer sheet in which exactly k of the available option letters are ticked. The string letters lists the option letters in strictly increasing alphabetical order, and each sheet is written as the ticked letters in that same order.

Implement ChoiceIterator. next() returns the following sheet, where sheets appear in ascending dictionary order, and hasNext() tells whether a sheet remains. The number of sheets can be large, so do not pre-compute them: each call may use O(k) time and the class should hold only O(k) extra state.

Example 1

Input:
operations = ["ChoiceIterator","next","hasNext","next","next","hasNext","next","hasNext"]arguments = [["dpqx",3],[],[],[],[],[],[],[]]
Output:
[null,"dpq",true,"dpx","dqx",true,"pqx",false]
Explanation:

The four 3-letter choices of d,p,q,x in alphabetical order are dpq, dpx, dqx, pqx.

Example 2

Input:
operations = ["ChoiceIterator","next","next","hasNext","next","hasNext"]arguments = [["kmw",1],[],[],[],[],[]]
Output:
[null,"k","m",true,"w",false]
Explanation:

With k = 1 every single letter is its own choice, in order k, m, w.

Example 3

Input:
operations = ["ChoiceIterator","hasNext","next","hasNext"]arguments = [["ace",3],[],[],[]]
Output:
[null,true,"ace",false]
Explanation:

When k equals the number of letters there is exactly one choice, the whole string.

Constraints

1 ≤ k ≤ letters.length ≤ 15

letters consists of distinct lowercase English letters sorted ascending

At most 104 calls; next is only called while hasNext() would return true.

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.
Time per case
Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms

Expected complexity

Time
O(k) per call
Space
O(k)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.