Iterator for Combination - Solution & Explanation

Problem Overview: Design an iterator that returns all combinations of length k from a given sorted string of characters. Each call to next() should return the next combination in lexicographical order, and hasNext() should indicate whether more combinations remain.

Approach 1: Precompute All Combinations (Time: O(C(n,k) * k), Space: O(C(n,k) * k))

This approach generates every valid combination during initialization using backtracking. Start from index 0, recursively build a string by choosing the next character and continuing until the length reaches k. Each completed combination is appended to a list. Because the input string is already sorted, the generated combinations naturally appear in lexicographic order. The iterator then simply maintains an index pointer: next() returns the current element and increments the pointer, while hasNext() checks whether the pointer is within bounds.

The main advantage is simplicity. Once the combinations are precomputed, each iterator call is constant time. The tradeoff is memory usage because all C(n,k) combinations are stored upfront.

Approach 2: Generate Combinations on the Fly (Time: O(C(n,k) * k), Space: O(k))

This approach generates the next combination only when needed instead of storing all results. Maintain an array of indices representing the current combination. Initially it contains [0,1,2,...,k-1]. When next() is called, build the string using those indices from the original characters.

To compute the next state, scan the indices from right to left and find the first position that can be incremented without exceeding its limit. Increase that index and reset all positions to its right to the smallest valid increasing sequence. This logic is similar to generating the next lexicographical combination and works well with an iterator design pattern. Only the current index array is stored, so the memory footprint stays small.

This technique avoids storing every combination and is typically preferred when the number of combinations is large. The time cost shifts from initialization to each call to next(), but each step still runs in about O(k).

Recommended for interviews: Interviewers usually expect the on‑the‑fly generation approach because it demonstrates understanding of string combination generation and iterator state management. Implementing the precomputation method first is still valuable because it proves you understand how combinations are formed. The optimized iterator version shows stronger design and algorithmic reasoning.