[Python] O(k) on the fly, explained
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 on
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:\n\n`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`.\nThis is the key remark of my method. Let us consider function `next()`:\n\n1. First we check if we already have some combination before, if not, just create the first one.\n2. 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.\n3. 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`.\n4. 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`.\n5. To implement `hashNext()` we just need to check if we reached the last state.\n\n**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.\n\n```\nfrom os.path import commonprefix\n\nclass CombinationIterator:\n\n    def __init__(self, characters, combinationLength):\n        self.c = characters\n        self.len = combinationLength\n        self.state = ""\n        \n    def next(self):\n        if self.state == "":\n            self.state = self.c[:self.len]\n        else:\n            end = len(commonprefix([self.c[::-1], self.state[::-1]]))\n            place = self.c.index(self.state[-end-1])\n            self.state = self.state[:-end-1] + self.c[place + 1: place + 2 + end]\n        return self.state\n\n    def hasNext(self):\n        return self.state != self.c[-self.len:]\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]