https://leetcode.com/problems/iterator-for-combination

There are different ways to solve this problem, one of them is to generate all possible combination and then when we asked to return next, just take the next one. Also we can use bitmasks, where we try to generate next combination and check if we choose correct number of elements or not. However I prefer to do it in a bit different way, I say it is honest iterator, where we find next permutation, given current one. Let me consider and example:

acfxyz, where we can use full alphabet. How can we find the next combination? We need to look at the end of our combination and try to increment it. Can we increment z? No, we can not, the same for y and x. What we can increment is f, so next combination will be acghij. This is the key remark of my method. Let us consider function next():

  1. First we check if we already have some combination before, if not, just create the first one.
  2. Now, we need to find the longest commont suffix, like we did in our example between current state and our string. I do this, using commonprefix function.
  3. Now, we need to find the place for previous symbol in our characters. Why? Because in our example we have alphabet abc...xyz, but we can have something like acdehkxyz, and we need to know, what is going after h. It is i? No, in this case it is k.
  4. Finally, we construct new state, taking first len(character) - end - 1 elements from previous state and adding end + 1 elements starting from place + 1 from our characters.
  5. To implement hashNext() we just need to check if we reached the last state.

Complexity of hasNext() is O(k), where k = combinationLength. Complexity of next() is also O(k), because we need to find the longest suffix, also we need to find element in string, using index() (this can be reduced to O(1), using hash table) and finally, we need to construct and return new state, which has length k, which can not be improved.

from os.path import commonprefix

class CombinationIterator:

    def __init__(self, characters, combinationLength):
        self.c = characters
        self.len = combinationLength
        self.state = ""
        
    def next(self):
        if self.state == "":
            self.state = self.c[:self.len]
        else:
            end = len(commonprefix([self.c[::-1], self.state[::-1]]))
            place = self.c.index(self.state[-end-1])
            self.state = self.state[:-end-1] + self.c[place + 1: place + 2 + end]
        return self.state

    def hasNext(self):
        return self.state != self.c[-self.len:]

If you like the solution, you can upvote it on leetcode discussion section: Problem 1286