1286. Iterator for Combination

Problem¶

Design CombinationIterator for a sorted string of distinct letters. Return its length-\(k\) combinations in lexicographical order; hasNext() checks availability without consuming a combination. Calls to next() are guaranteed valid.

CombinationIterator("abc", 2)
next() → "ab"
hasNext() → True
next() → "ac"
next() → "bc"
hasNext() → False

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        pass

    def next(self) -> str:
        pass

    def hasNext(self) -> bool:
        pass

Key trick¶

Represent each combination by increasing indices; increment the rightmost index that can advance, then reset its suffix to consecutive indices.

characters = "abcd", k = 3
indices: [0,1,2] → [0,1,3] → [0,2,3] → [1,2,3]
result:   "abc"  →   "abd"  →   "acd"  →   "bcd"

Trap¶

Index i cannot exceed \(n-k+i\) because later indices need room; repeated hasNext() calls must not advance the iterator.

Why is it interesting?¶

It turns backtracking into a compact, resumable state machine without generating all \(\binom{n}{k}\) combinations.

Python solution¶

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        self.characters = characters
        self.indices = list(range(combinationLength))
        self.done = False

    def next(self) -> str:
        indices = self.indices
        n, k = len(self.characters), len(indices)
        s = "".join(self.characters[i] for i in indices)

        # Find the rightmost index that has room to advance.
        i = k - 1
        while i >= 0 and indices[i] == n - k + i:
            i -= 1

        if i < 0:
            self.done = True
        else:
            indices[i] += 1

            # Choose the smallest valid suffix for lexicographical order.
            for j in range(i + 1, k):
                indices[j] = indices[j - 1] + 1

        return s

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

With \(n\) characters and combination length \(k\):

Initialization: \(O(k)\) time.
next(): \(O(k)\) time.
hasNext(): \(O(1)\) time.
Auxiliary space: \(O(k)\).

Comment on my solution¶

Your recursive backtracking correctly generates combinations in lexicographical order, but storing every result costs \(O(k\binom{n}{k})\) space. The explicit-stack attempt is unfinished; the increasing-index representation preserves exactly the state needed to resume, without simulating recursive frames.

# Ideas:
# - dfs/backtracking to generate all combinations
#   - then how to do it lazily
# - If we can turn the backtracking recurrence function into
#   an iterative program simulating the recurrence with a stack
#   we could store the stack and do one turn at each next() call
# - I don't know how to solve this problem
#
# characters = "abcd"
# length = 3
# res = []
# path = []
# def backtracking(i):
#     if len(path) == length:
#         res.append("".join(path))
#         return
#     remaining = length - len(path)
#     for j in range(i, len(characters) - remaining + 1):
#         path.append(characters[j])
#         backtracking(j + 1)
#         path.pop()
# backtracking(0)
#
#
# characters = "abcd"
# length = 3
# res = []
# path = []
# stack = [(j, start, end)]
#
# while stack:
#     if len(path) == length:
#         res.append("".join(path))
#     j, start, end = stack.pop()
#     if j < end:
#         stack.append((j + 1, start, end))
#     remaining = length - len(path)

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):


    def next(self) -> str:


    def hasNext(self) -> bool: