We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Iterator for Combination

Number: 1211

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Design a CombinationIterator class that, given a string of sorted distinct lowercase letters and a combination length, precomputes all combinations of the given length in lexicographical order. Then, implement the next() method to return the next combination and the hasNext() method to check if there are more combinations.

Key Insights

  • The problem involves generating all possible combinations of a fixed length from the given characters.
  • Since the characters are already sorted, combinations generated using backtracking will automatically be in lexicographical order.
  • Precompute all combinations using backtracking and store them in a list; then simply iterate through the list using an index pointer.
  • Given the constraints, precomputing combinations has a manageable cost.
  • Each call to next() and hasNext() should work in constant time after the precomputation step.

Space and Time Complexity

Time Complexity: Precomputation takes O(CombinationCount * k), where CombinationCount = C(n, k) and k is the combinationLength; each next() and hasNext() call is O(1).
Space Complexity: O(CombinationCount * k) to store all combinations.

Solution

The approach is to generate all possible combinations using backtracking and store them in an array (or equivalent data structure). When next() is called, return the current combination and increment the pointer; hasNext() simply checks if the pointer has reached the end of the precomputed list. This separation allows constant time retrieval of combinations after the initial O(CombinationCount * k) computation. The distinct characters and sorted order guarantee that the backtracking method yields combinations in lexicographical order without additional sorting.

Code Solutions

# CombinationIterator class in Python
class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        # List to store precomputed combinations
        self.combinations = []
        # Pointer to track current position in combinations list
        self.index = 0
        # Helper function for backtracking to generate combinations
        def backtrack(start: int, path: list):
            # If the current combination has reached the desired length, add it to the list
            if len(path) == combinationLength:
                self.combinations.append(''.join(path))
                return
            # Generate combinations by iterating over the remaining characters
            for i in range(start, len(characters)):
                path.append(characters[i])
                backtrack(i + 1, path)
                path.pop()  # backtrack: remove last character
        # Start backtracking from index 0 with an empty path
        backtrack(0, [])
    
    def next(self) -> str:
        # Return the current combination then increment pointer
        result = self.combinations[self.index]
        self.index += 1
        return result

    def hasNext(self) -> bool:
        # Check if there are more combinations left
        return self.index < len(self.combinations)
← Back to All Questions