Design an Iterator class, which has:

A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
A function next() that returns the next combination of length combinationLength in lexicographical order.
A function hasNext() that returns True if and only if there exists a next combination.

 
Example:
CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.

iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

 
Constraints:

1 <= combinationLength <= characters.length <= 15
There will be at most 10^4 function calls per test.
It's guaranteed that all calls of the function next are valid.

Difficulty: interview

Starter code:

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
    def next(self) -> str:
    def hasNext(self) -> bool:
# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

Solutions:
class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        self.nextCombIt = combinations(characters, combinationLength)
        self.nextComb = next(self.nextCombIt, None)

    def __next__(self) -> str:
        nextComb = self.nextComb
        self.nextComb = next(self.nextCombIt, None)
        return ''.join(nextComb)

    def hasNext(self) -> bool:
        return self.nextComb is not None


from itertools import combinations
from math import factorial
class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.base = characters
        self.start = 0
        self.end = factorial(len(characters)) / factorial(combinationLength) / factorial(len(characters)-combinationLength)
        self.strBase = combinations(characters, combinationLength)

    def __next__(self) -> str:
        if self.hasNext():
            self.start += 1
            val = next(self.strBase)
            return ''.join(val)
        else:
            raise StopIteration

    def hasNext(self) -> bool:
        return self.start < self.end
        


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()


class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.combinations = self.get_combinations(characters,combinationLength,0)        
        self.next_item=0

    def next(self) -> str:
        ans= self.combinations[self.next_item]
        self.next_item+=1
        return \"\".join(ans)

    def hasNext(self) -> bool:
        return self.next_item < len(self.combinations)

    def get_combinations(self,chars, k, start):
        ans = []
        if k == 0:
            return ans
        if k==1:
            return [[char] for char in chars[start:] ]
        count = 0
        for c in chars[start:]:
            for comb in self.get_combinations(chars, k - 1,start+count+1):
                    temp = []
                    temp.append(c)
                    temp.extend(comb)
                    ans.append(temp)
            count+=1
        return ans

            
        
        
        

# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

class CombinationIterator:

    def __init__(self, arr: str, l: int):
        self.result = []
        self.idx = 0
        n = len(arr)
        
        self.backtrack(arr, 0, l, n, \"\")
                        
    def backtrack(self, arr, left, ln, n, currStr):
        if ln == 0:
            self.result.append(\"\".join(sorted(currStr)))
            return
        
        for i in range(left, n):
            
            newStr = currStr
            newStr += arr[i]
            
            self.backtrack(arr, i+1, ln-1, n, newStr)
        

    def next(self) -> str:
        res = self.result[self.idx]
        self.idx += 1
        return res
        

    def hasNext(self) -> bool:
        if self.idx >= len(self.result):
            return False
        
        return True


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.combs = []
        
        n = len(characters)
        # the order in self.combs is reverse lexicographical by going from bitmask of 0 upwards
        for bitmask in range((1<<n)): 
            if bin(bitmask).count('1') == combinationLength: 
                curr = []
                for j in range(n): 
                    if bitmask & (1 << n-j-1): 
                        curr.append(characters[j])
                self.combs.append(''.join(curr))


    def __next__(self) -> str:
        return self.combs.pop()

    def hasNext(self) -> bool:
        return self.combs


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()


class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.characters = characters
        self.len = combinationLength
        self.dic = deque([x for x in itertools.combinations(self.characters,self.len)])

    def next(self) -> str:
        x = self.dic.popleft()
        return \"\".join(x)
        
    def hasNext(self) -> bool:
        if len(self.dic) != 0:
            return True
        return False


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        def dfs(start, path):
            if len(path)==self.combinationLength:
                yield ''.join(path)
            else:
                for i in range(start, len(self.characters)):
                    path.append(self.characters[i])
                    yield from dfs(i+1, path)
                    path.pop()
        
        self.characters = sorted(characters)
        self.combinationLength = combinationLength
        self.next_val = None
        self.comb = dfs(0, [])
 
    def __next__(self) -> str:
        if self.next_val:
            tmp = self.next_val
            self.next_val = None
            return tmp
        else:
            return next(self.comb)

    def hasNext(self) -> bool:
        if self.next_val:
            return True
        else:
            self.next_val = next(self.comb,False)
            return bool(self.next_val)

# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()


class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.combinations = []
        self.characters = characters
        self.combinationLength = combinationLength
        
    
        def backtrack(characters,res,cur,index):
            if len(cur) == combinationLength:
                #print(cur)
                res.append(\"\".join(cur[:]))
                return
            for i in range(index,len(self.characters)):
                cur.append(self.characters[i])
                #print(cur)
                backtrack(characters,res,cur,i+1)
                cur.pop()
        
        backtrack(characters,self.combinations,[],0)
        self.combinationsQueue = deque(self.combinations)
        print(self.combinationsQueue)
    def next(self) -> str:
        if self.combinationsQueue:
            return self.combinationsQueue.popleft()

    def hasNext(self) -> bool:
        return len(self.combinationsQueue) > 0
        


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.combinations = []
        self.characters = characters
        self.combinationLength = combinationLength
        
    
        def backtrack(characters,res,cur,index):
            if len(cur) == combinationLength:
                #print(cur)
                res.append(\"\".join(cur[:]))
                return
            for i in range(index,len(self.characters)):
                cur.append(self.characters[i])
                #print(cur)
                backtrack(characters,res,cur,i+1)
                cur.pop()
        
        backtrack(characters,self.combinations,[],0)
        self.combinationsQueue = deque(self.combinations)
        #print(self.combinationsQueue)
    def next(self) -> str:
        if self.combinationsQueue:
            return self.combinationsQueue.popleft()

    def hasNext(self) -> bool:
        return len(self.combinationsQueue) > 0
        


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

from queue import Queue
class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        
        self.characters=characters
        self.combinationLength=combinationLength
        self.arr=[0]*26
        for i in self.characters:
            temp=ord(i)
         
            self.arr[temp-97]+=1
            
        
        self.q=Queue(maxsize=10001)
        self.solve(self.arr,self.combinationLength,self.q,0,\"\")
        
        
        
    
    
    def solve(self,arr,sizee,bag,ind,cur):
        if(len(cur)==sizee):
            bag.put(cur)
            return bag
        
        
        for i in range(ind,26):
            if(arr[i]!=0):
                arr[i]-=1
                bag=self.solve(arr,sizee,bag,i,cur+chr(i+97))
            
                arr[i]+=1
        
        return bag
                
                
                
                
        

    def next(self) -> str:
        
        return self.q.get()

    def hasNext(self) -> bool:
        return not self.q.empty()
        


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

def rec(s, l, arr, current):
    for i in range(len(s)):
        current.append(s[i])
        if len(current)==l:
            arr.append(''.join(current))
        rec(s[i+1:],l,arr,current)
        current.pop(len(current)-1)
        

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.characters = characters
        self.combinationLength = combinationLength
        self.index = 0
        self.arr = []
        c = []
        rec(characters, combinationLength, self.arr,c)

    def __next__(self) -> str:
        ret = self.arr[self.index]
        self.index+=1
        return ret

    def hasNext(self) -> bool:
        if self.index<len(self.arr):
            return True
        return False


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()


class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.input_string = characters
        self.queue = []
        self.combinationLength = combinationLength
        self.generate(0, '')
        
    def generate(self, start_index, acc_string):
        if len(acc_string)==self.combinationLength:
            self.queue.append(acc_string) 
            return
        
        for i in range(start_index, len(self.input_string)):
            self.generate(i+1, acc_string + self.input_string[i])
        
    def __next__(self) -> str:
        return self.queue.pop(0)

    def hasNext(self) -> bool:
        return len(self.queue)!=0


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()


class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.comb = list(map(lambda x: \"\".join(x), list(itertools.combinations(characters,combinationLength))))[::-1]


    def next(self) -> str:
        return self.comb.pop()

    def hasNext(self) -> bool:
        return (len(self.comb) != 0)      


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.N = combinationLength
        self.cl = len(characters)
        self.sym = characters
        self.precom = self.__pre(self.cl, combinationLength)
        self.index = len(self.precom)-1
    def __next__(self) -> str:
        curr = self.precom[self.index]
        res = []
        for i,c in enumerate(curr):
            if c == '1':
                res.append(self.sym[i])
        self.index -= 1
        return ''.join(res)
    def hasNext(self) -> bool:
        if self.index < 0:
            return False
        return True
    def __pre(self, N, M):
        maxi = 2**N
        res = []
        for curr in range(maxi):
            binary = bin(curr)[2:]
            if binary.count('1') == M:
                res.append(binary.zfill(N))
        return res

# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()




class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.chars = characters
        self.n = combinationLength
        self.inds = [i for i in range(combinationLength)]
        self.iMax = len(self.chars)
        self.gotNext = True

    def __next__(self) -> str:
        print((self.inds))
        ans = ''.join([self.chars[i] for i in self.inds])
        c = 1
        i = self.n -1
        while i >= 0 and c == 1:
            if self.inds[i] == self.iMax-self.n+i:
                c = 1
            else:
                c = 0
            i -= 1
        if i == -1 and c == 1:
            self.gotNext = False
        else:
            self.inds[i+1] += 1
            for j in range(i+2, self.n):
                self.inds[j] =  self.inds[j-1] +1
        
        
#         for i in range(self.n-1, -1 ,-1):
#             self.inds[i] += c
#             if self.inds[i] == self.iMax-self.n+i+1:
#                 if i != 0:
#                     self.inds[i] = self.inds[i-1] + 2
#                     c = 1
#                 else:
#                     self.gotNext = False
#             else:
#                 c = 0
        return ans

    def hasNext(self) -> bool:
        return self.gotNext


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()


class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.combs = list(combinations(characters, combinationLength))
        self.idx = 0
        

    def next(self) -> str:
        chars = self.combs[self.idx]
        self.idx += 1
        return \"\".join(chars)
        

    def hasNext(self) -> bool:
        return self.idx < len(self.combs)
        
        


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.nums = [i for i in range(combinationLength)]
        self.characters = characters
        self.s = len(characters)
        self.len = combinationLength
        self.is_next = True
        
    def __next__(self) -> str:
        ret = ''
        for n in self.nums:
            ret += self.characters[n]
        
        self.nums[-1] += 1
        if self.nums[-1] == self.s:
            carry = True
            cnt = -2
            while carry and cnt >= -self.len:
                self.nums[cnt] += 1
                if self.nums[cnt] > self.s + cnt:
                    carry = True
                    cnt -= 1
                else:
                    carry = False
        
            if cnt < -self.len:
                self.is_next = False
            else:
                for i in range(cnt+1, 0, 1):
                    self.nums[i] = self.nums[i-1] + 1
                
        # print(self.nums)
        return ret
    
    def hasNext(self) -> bool:
        return self.is_next


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()


class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.s=characters
        self.k=combinationLength
        self.r=[]
        self.dfs('',0)
    def dfs(self,st,idx):
        if len(st)==self.k:
            self.r.append(st)
            return
        for i in range(idx,len(self.s)):
            self.dfs(st+self.s[i],i+1)

    def __next__(self) -> str:
        return self.r.pop(0)
        

    def hasNext(self) -> bool:
        return len(self.r)!=0
        


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()


import itertools

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        char_arr = list(characters)
        self.data = itertools.combinations(char_arr, combinationLength)
        self.count = len(list(itertools.combinations(char_arr, combinationLength)))

    def __next__(self) -> str:
        ans = ''.join(next(self.data, ''))
        self.count -= 1
        return ans

    def hasNext(self) -> bool:
        return self.count > 0


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()


class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.chs = characters
        self.comblen = combinationLength
        self.totlen = len(self.chs)
        self.idx = [_ for _ in range(self.comblen)]
        self.idx[-1] -= 1


    def __next__(self) -> str:
        k = self.comblen  # the digit where the calculation stop propagating
        while k > 0:
            k -= 1
            self.idx[k] += 1
            if self.idx[k] < self.totlen + k + 1 - self.comblen:
                break
        for i in range(k+1, self.comblen):
            self.idx[i] = self.idx[i-1] + 1

        return ''.join([self.chs[k] for k in self.idx])

    def hasNext(self) -> bool:
        return self.idx[0] != self.totlen - self.comblen
        


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()


class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.last = None
        self.end = characters[-combinationLength:]
        self.gen = self.gen_comb(characters, 0, [], combinationLength)
    
    def gen_comb(self, char, start, buffer, length):
        if len(buffer) == length:
            yield ''.join(buffer)
            return
        
        for i in range(start, len(char)):
            yield from self.gen_comb(char, i+1, buffer+[char[i]], length)
        
    def __next__(self) -> str:
        self.last = next(self.gen)
        return self.last  

    def hasNext(self) -> bool:
        return self.last != self.end
        


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()


class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.combo = []
        self.find_combo(0, combinationLength, characters, \"\")
        self.combo.sort()
        self.pos = -1
        
        

    def next(self) -> str:
        self.pos += 1
        
        return self.combo[self.pos]
        
        
    def hasNext(self) -> bool:
        return self.pos + 1 < len(self.combo)
    
    def find_combo(self, idx, end, characters, cur):
        if idx == len(characters):
            if len(cur) == end:
                self.combo.append(cur[:])
        
        else:
            self.find_combo(idx + 1, end, characters, cur + characters[idx])
            self.find_combo(idx + 1, end, characters, cur)
            
            
        
        


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()