LeetCode 1286 - Iterator for Combination

The problem asks us to design a class CombinationIterator that generates all combinations of a given length from a strin

leetcodemediumstringbacktrackingdesigniterator

LeetCode Problem 1286

Difficulty: 🟡 Medium
Topics: String, Backtracking, Design, Iterator

Solution

Problem Understanding

The problem asks us to design a class CombinationIterator that generates all combinations of a given length from a string of sorted, distinct lowercase letters. The iterator must return these combinations in lexicographical order, meaning alphabetically.

The input consists of two components: a string characters, which contains unique letters sorted in ascending order, and an integer combinationLength, specifying the size of each combination. The expected output from next() is the next combination in lexicographical order, and hasNext() should indicate whether more combinations are available.

The constraints limit characters to at most length 15 and guarantee valid calls to next(). This ensures that we never request a combination beyond what exists, and it also keeps the total number of combinations manageable since 15 choose 7 (maximum mid-point for combinations) is 6435, which is computationally feasible.

Important edge cases include combinationLength equal to 1 (returning individual characters), combinationLength equal to the length of characters (returning the string itself), and situations where repeated calls to next() exhaust all combinations. The input guarantees uniqueness of characters, so we do not need to handle duplicates.

Approaches

A brute-force approach would generate all possible combinations upfront and store them in a list. This ensures next() and hasNext() are trivial to implement by moving an index along the list. However, generating all combinations in advance can be expensive in memory and unnecessary if not all combinations are requested.

The key observation for a better solution is that combinations can be generated lazily, i.e., only when next() is called, using an index array to track the current combination. This allows us to generate the next combination efficiently in lexicographical order without storing all combinations at once.

Approach Time Complexity Space Complexity Notes
Brute Force O(C(n, k)) O(C(n, k) * k) Precompute all combinations and iterate through them.
Optimal O(k) per next() O(k) Track current combination indices and update in lexicographical order on the fly.

Algorithm Walkthrough

  1. Initialize an array indices of size combinationLength containing the first combinationLength indices [0, 1, ..., combinationLength-1]. This represents the first combination of characters.
  2. Maintain a flag has_next indicating whether more combinations exist. Initially, it is True.
  3. In the next() method, convert the current indices into the corresponding combination string and prepare the indices for the next combination.
  4. To advance indices to the next combination, start from the rightmost index and try to increment it. If it reaches the maximum allowed value (n - (combinationLength - i)), move left until an increment is possible, then reset all subsequent indices sequentially.
  5. If no index can be incremented, set has_next to False.
  6. The hasNext() method simply returns the has_next flag.

Why it works: The invariant is that indices always represent a valid lexicographical combination. Incrementing the rightmost possible index ensures that we generate combinations in strict order without skipping any.

Python Solution

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.characters = characters
        self.combinationLength = combinationLength
        self.indices = list(range(combinationLength))
        self.has_next = True

    def next(self) -> str:
        if not self.has_next:
            return ""
        # Generate the current combination string
        current = ''.join(self.characters[i] for i in self.indices)
        # Prepare indices for the next combination
        n = len(self.characters)
        i = self.combinationLength - 1
        while i >= 0 and self.indices[i] == n - self.combinationLength + i:
            i -= 1
        if i < 0:
            self.has_next = False
        else:
            self.indices[i] += 1
            for j in range(i + 1, self.combinationLength):
                self.indices[j] = self.indices[j - 1] + 1
        return current

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

The Python implementation initializes indices to represent the first combination. Each call to next() generates the current combination string and updates indices to the next valid combination. The has_next flag efficiently tracks whether more combinations remain.

Go Solution

type CombinationIterator struct {
    characters string
    combinationLength int
    indices []int
    hasNext bool
}

func Constructor(characters string, combinationLength int) CombinationIterator {
    indices := make([]int, combinationLength)
    for i := 0; i < combinationLength; i++ {
        indices[i] = i
    }
    return CombinationIterator{characters: characters, combinationLength: combinationLength, indices: indices, hasNext: true}
}

func (this *CombinationIterator) Next() string {
    if !this.hasNext {
        return ""
    }
    current := make([]byte, this.combinationLength)
    for i, idx := range this.indices {
        current[i] = this.characters[idx]
    }
    n := len(this.characters)
    i := this.combinationLength - 1
    for i >= 0 && this.indices[i] == n - this.combinationLength + i {
        i--
    }
    if i < 0 {
        this.hasNext = false
    } else {
        this.indices[i]++
        for j := i + 1; j < this.combinationLength; j++ {
            this.indices[j] = this.indices[j-1] + 1
        }
    }
    return string(current)
}

func (this *CombinationIterator) HasNext() bool {
    return this.hasNext
}

The Go implementation mirrors the Python logic, with the main differences being slice handling and explicit byte-to-string conversion. The indices slice and hasNext flag serve the same roles.

Worked Examples

Example: CombinationIterator("abc", 2)

Step indices Current Combination hasNext
Init [0,1] "ab" True
Call next() [0,1] → [0,2] "ab" True
Call next() [0,2] → [1,2] "ac" True
Call next() [1,2] → none "bc" False

At each step, the rightmost incrementable index is updated, and all subsequent indices are reset, generating all combinations in lexicographical order.

Complexity Analysis

Measure Complexity Explanation
Time O(k) per next() Updating indices and generating a string of length k.
Space O(k) Only the indices array of size combinationLength is stored.

The algorithm does not precompute all combinations, saving significant space. Each next() call performs only a bounded number of operations proportional to combinationLength.

Test Cases

# provided example
obj = CombinationIterator("abc", 2)
assert obj.next() == "ab"  # first combination
assert obj.hasNext() is True
assert obj.next() == "ac"  # second combination
assert obj.hasNext() is True
assert obj.next() == "bc"  # third and last combination
assert obj.hasNext() is False

# edge case: combinationLength = 1
obj = CombinationIterator("xyz", 1)
assert obj.next() == "x"
assert obj.next() == "y"
assert obj.next() == "z"
assert obj.hasNext() is False

# edge case: combinationLength = length of characters
obj = CombinationIterator("pqrs", 4)
assert obj.next() == "pqrs"
assert obj.hasNext() is False

# edge case: last combination reached immediately after initialization
obj = CombinationIterator("a", 1)
assert obj.next() == "a"
assert obj.hasNext() is False
Test Why
"abc", 2 Normal operation with multiple combinations
"xyz", 1 Single-character combinations
"pqrs", 4 Combination length equal to string length
"a", 1 Minimal input with immediate exhaustion

Edge Cases

One edge case is combinationLength = 1, where each character in the string is a combination. This can trip up implementations that assume multiple characters per combination. Our approach handles it naturally because the indices array still represents positions correctly.

Another edge case is when combinationLength equals the length of characters. There is only one valid combination, and next() should immediately return the string and set hasNext to false. The rightmost index increment logic handles this without additional conditions.

A third edge case is repeated calls to next() after exhausting all combinations. Because hasNext is set to false when no further increment is possible, subsequent next() calls return an empty string instead of producing errors or invalid combinations. This ensures safe behavior under repeated calls.