Iterator for Combination

MediumBacktrackingbacktracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Implement CombinationIterator(characters, combinationLength), where characters is a string of distinct lowercase letters in sorted order. The iterator walks through every way to choose combinationLength letters from characters (keeping their original relative order within each choice), in **lexicographic** order. - next() returns the next combination as a string. It is only called when hasNext() is true. - hasNext() returns true if at least one combination has not been returned yet.

Examples

Input: ["CombinationIterator","next","hasNext","next","hasNext","next","hasNext"] [["abc",2],[],[],[],[],[],[]]
Output: [null,"ab",true,"ac",true,"bc",false]
The combinations of size 2 in order are "ab", "ac", "bc". After the third one there is nothing left.
Input: ["CombinationIterator","hasNext","next","hasNext"] [["wxyz",4],[],[],[]]
Output: [null,true,"wxyz",false]
Choosing all 4 letters gives exactly one combination.

Constraints

  • 1 <= combinationLength <= characters.length <= 15
  • `characters` has distinct lowercase letters in increasing order
  • At most 10^4 calls to `next` and `hasNext`
  • `next` is only called when a combination remains

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More backtracking problems