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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Iterator for Combination

Difficulty: Medium

Problem Description

Design the CombinationIterator class that initializes with a string of sorted distinct lowercase English letters and a number indicating the length of combinations. The class should support two methods: next(), which returns the next combination in lexicographical order, and hasNext(), which indicates if any combinations remain.

Key Insights

  • The problem requires generating combinations of a specified length from a given set of characters.
  • The combinations must be generated in lexicographical order.
  • The algorithm needs to efficiently keep track of the current combination to return the next combination on the next() call.
  • The maximum length of characters is 15, which allows for combinations to be generated without excessive performance concerns.

Space and Time Complexity

Time Complexity: O(1) for hasNext() and O(k) for next(), where k is the combination length. Generating all combinations takes O(n choose k) overall.
Space Complexity: O(n choose k) for storing all combinations (if precomputed) or O(k) for storing the current combination.

Solution

The solution involves using a backtracking approach to generate combinations. The CombinationIterator class will maintain a list of all possible combinations and an index to track the current position. The next() function retrieves the combination at the current index and increments it, while hasNext() checks if the current index is less than the total number of combinations.

Code Solutions

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        from itertools import combinations
        self.combinations = sorted([''.join(comb) for comb in combinations(characters, combinationLength)])
        self.index = 0

    def next(self) -> str:
        result = self.combinations[self.index]
        self.index += 1
        return result

    def hasNext(self) -> bool:
        return self.index < len(self.combinations)
← Back to All Questions