Problem Breakdown
We need to implement a class that acts as an iterator over combinations of length combinationLength from the input string. The core requirements are maintaining state between calls (next() and hasNext()) and ensuring results follow lexicographical order. Since the input characters is guaranteed to be sorted, we can rely on Depth-First Search (DFS) traversal logic to generate combinations in the correct order naturally without additional sorting steps.
Intuition
- State Management: An iterator requires remembering where it left off. We use an index pointer (
self.idx) pointing into a list of pre-computed results. - Ordering Guarantee: Because
charactersis sorted and unique, iterating indices from to in our backtracking function ensures that combinations are generated lexicographically (e.g., ‘ab’ comes before ‘ac’). - Pre-computation vs. Lazy Generation: While a true iterator might suggest generating the next combination on demand ( space), doing so requires complex logic to find the “next” valid index configuration without backtracking every time. Given , pre-generating all combinations fits easily in memory and simplifies
next()/hasNext()to simple array access operations, which is often preferred for interview efficiency unless strict space constraints exist (which they don’t here).
Approach
- Initialization (
__init__):- Initialize an empty list
self.combinations. - Define a recursive helper function
backtrack(start_index, current_path). - Base case: If path length equals
combinationLength, join the characters and append toself.combinations. - Recursive step: Iterate through available indices starting from
start_indexto ensure unique combinations (no duplicates). Recurse with incremented index. Backtrack by popping after recursion returns.
- Initialize an empty list
- Next (
next):- Retrieve the string at current
self.idx. - Increment
self.idx. - Return the retrieved combination.
- Retrieve the string at current
- Has Next (
hasNext):- Check if
self.idxis within bounds ofself.combinations.
- Check if
Complexity Analysis
- Time Complexity:
- Initialization: , where we generate every valid combination and join characters (cost proportional to length). For , combinations. This is negligible for modern hardware.
next(): due to string retrieval/copying, effectively amortized constant relative to input size constraints.hasNext(): .
- Space Complexity:
- Initialization: to store the list of strings and recursion stack depth (). With max combinations and string length , memory usage is well within limits (typically < 20MB).
Solution
class CombinationIterator:
def __init__(self, characters: str, combinationLength: int):
self.combinations = []
self.idx = 0
# Helper function to generate combinations via backtracking
# Since 'characters' is sorted and unique, DFS naturally yields lexicographical order.
def backtrack(start_idx, current_path):
if len(current_path) == combinationLength:
self.combinations.append("".join(current_path))
return
for i in range(start_idx, len(characters)):
# Add character to path and recurse with next index
current_path.append(characters[i])
backtrack(i + 1, current_path)
current_path.pop() # Backtrack
backtrack(0, [])
def next(self):
if self.idx < len(self.combinations):
res = self.combinations[self.idx]
self.idx += 1
return res
def hasNext(self):
return self.idx < len(self.combinations)
Edge Cases Handled
- Single Combination: If
combinationLengthequals the length ofcharacters, only one combination exists. The logic correctly appends it once and returns false on subsequent checks viahasNext(). - Full String Usage: Handles cases where we must use all characters (e.g., input “abc”, len 3).
- Memory Constraints: Leverages Python’s list storage which is efficient enough for , avoiding the complexity of implementing a custom iterator state machine that would be harder to debug in an interview setting.