Design the CombinationIterator class:
CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.next() Returns the next combination of length combinationLength in lexicographical order.hasNext() Returns true if and only if there exists a next combination.
Example 1:
Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]
Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next(); // return "ab"
itr.hasNext(); // return True
itr.next(); // return "ac"
itr.hasNext(); // return True
itr.next(); // return "bc"
itr.hasNext(); // return False
Constraints:
1 <= combinationLength <= characters.length <= 15characters are unique.104 calls will be made to next and hasNext.next are valid.In this approach, we precompute all the combinations of the given string of a specified length. This allows us to provide the next combination in constant time by just iterating over the precomputed list. For this, we can use recursion or libraries to generate combinations initially and store them in an internal data structure.
To find all combinations of a particular length, you can use backtracking or an iterative process that resembles a binary-like increase in combinations selection.
This Python solution uses the itertools.combinations library to generate all the combinations of the given length at the initialization stage. Whenever next() is called, it returns the current combination and advances the index.
C++
Time Complexity: O(n!) for precomputation, O(1) for next and hasNext.
Space Complexity: O(n!) due to storage of combinations.
Instead of generating all combinations at once, we can generate them on the fly when next() is called. This approach uses bit manipulation to generate the combination efficiently by representing each combination as a bitmask. However, this requires understanding how to generate valid combinations incrementally with proper bit manipulation.
This C# solution uses an indices array to represent the current combination. It simulates the generation of combinations by modifying the indices array with each call to next(). When there is a valid combination, the indices are updated to represent the next viable combination.
JavaScript
Time Complexity: O(1) for next and hasNext, average complexity due to combination generation logic.
Space Complexity: O(combinationLength), the storage used for the indices.
| Approach | Complexity |
|---|---|
| Precompute All Combinations | Time Complexity: |
| Generate Combinations on The Fly | Time Complexity: |
Combinations - Leetcode 77 - Python • NeetCode • 78,575 views views
Watch 9 more video solutions →Practice Iterator for Combination with our built-in code editor and test cases.
Practice on FleetCode