Problem statement

https://binarysearch.com/problems/Lexicographic-Combination-Iterator/

Solution

Equal to Leetcode 1286. Iterator for Combination.

Complexity

It is O(k) for time and and space for next and hasnext.

Code

from os.path import commonprefix

class LexicographicCombinationIterator:
    def __init__(self, c, k):
        self.c = c
        self.k = k
        self.state = ""
        
    def next(self):
        if self.state == "":
            self.state = self.c[:self.k]
        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.k:]