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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Complete search

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


class CombinationIterator:

	def __init__(self, characters: str, combinationLength: int):
		self.combs = []
		n = len(characters)
		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


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)


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


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


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


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
		return ans

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


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
		return ret

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


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


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


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
		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


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