Skip to content
MediumStringsAI interview only

Iterator for Combination

Asked atgoogleamazonmicrosoft

01 · Problem

Design an iterator over all combinations of a fixed length drawn from a string of characters.

Implement the CombinationIterator class:

  • CombinationIterator(String characters, int combinationLength) receives a string of sorted, distinct lowercase letters and the length of each combination.
  • String next() returns the next combination of length combinationLength in lexicographic order. Characters inside a combination keep their original order from characters.
  • boolean hasNext() returns true if at least one more combination remains, otherwise false.

Every call to next is guaranteed to be valid (there is always a combination left when it is called).

02 · Examples

Example 01
Input
["CombinationIterator","next","next","hasNext","next","next","next","next","hasNext"], [["pqrs",2],[],[],[],[],[],[],[],[]]
Output
[null,"pq","pr",true,"ps","qr","qs","rs",false]

The 2-letter combinations of "pqrs" in lexicographic order are pq, pr, ps, qr, qs, rs. After rs is returned there are none left.

Example 02
Input
["CombinationIterator","next","next","next","next","hasNext"], [["wxyz",3],[],[],[],[],[]]
Output
[null,"wxy","wxz","wyz","xyz",false]

The 3-letter combinations of "wxyz" are wxy, wxz, wyz, xyz in order; after all four, hasNext is false.

Example 03
Input
["CombinationIterator","hasNext","next","hasNext"], [["k",1],[],[],[]]
Output
[null,true,"k",false]

With a single character and length 1 there is exactly one combination, "k".

03 · Constraints

  • 011 <= combinationLength <= characters.length <= 15
  • 02characters consists of sorted, distinct lowercase English letters
  • 03At most 104 calls in total are made to next and hasNext
  • 04Every call to next is valid

04 · Optimal complexity

Time
O(k) per next, O(1) per hasNext
Space
O(k)
05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem