Iterator for Combination

MEDIUM

Description

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 <= 15
All the characters of characters are unique.
At most 10⁴ calls will be made to next and hasNext.
It is guaranteed that all calls of the function next are valid.

Approaches

Checkout 2 different approaches to solve Iterator for Combination. Click on different approaches to view the approach and algorithm in detail.

Approach 2: On-the-fly Generation with Indices

This highly efficient approach avoids pre-computing all combinations. Instead, it calculates the next combination only when the next() method is called. It maintains the state of the current combination using an array of indices that point to characters in the input string, a technique often used for generating combinations iteratively.

Algorithm

CombinationIterator(characters, combinationLength):
1. Store characters, its length n, and combinationLength k.
2. Initialize an integer array indices of size k.
3. Populate indices to represent the first combination: indices[i] = i for i from 0 to k-1.
4. Set a boolean flag hasNextFlag = true.
next():
1. Build the result string for the current combination by looking up characters using the values in the indices array.
2. Prepare the indices for the next call. Find the rightmost index i that can be incremented. An index indices[i] can be incremented if it's not at its maximum possible value, which is i + n - k.
3. Scan from i = k-1 down to 0 to find the first index that is not at its maximum value.
4. If no such index is found, it means the current combination is the last one. Set hasNextFlag = false.
5. If an index i is found: a. Increment indices[i]. b. For all subsequent indices j > i, set indices[j] = indices[j-1] + 1 to form the next lexicographically smallest combination.
6. Return the string built in step 1.
hasNext():
1. Return the hasNextFlag.

The state of the iterator is represented by an array of integers, indices, of size combinationLength. Each integer in this array is an index into the original characters string. The constructor initializes this array to [0, 1, ..., k-1], representing the first lexicographical combination.

The next() method performs two main tasks: it first constructs the string for the current indices and then updates the indices array to point to the next combination. To find the next combination, we scan the indices array from right to left, looking for the first index we can increment. Once we find such an index, we increment it and then reset all subsequent indices to be consecutive values following it. This guarantees that we move to the very next combination in lexicographical order. If we scan the whole array and find that all indices are at their maximum possible values, we know there are no more combinations left.

class CombinationIterator {
    private String characters;
    private int n;
    private int k;
    private int[] indices;
    private boolean hasNext;

    public CombinationIterator(String characters, int combinationLength) {
        this.characters = characters;
        this.n = characters.length();
        this.k = combinationLength;
        this.indices = new int[k];
        // Initialize to the first combination: [0, 1, ..., k-1]
        for (int i = 0; i < k; i++) {
            this.indices[i] = i;
        }
        this.hasNext = true;
    }

    public String next() {
        // Build the current combination string
        StringBuilder sb = new StringBuilder();
        for (int index : indices) {
            sb.append(characters.charAt(index));
        }
        
        // Find the next combination's indices for the subsequent call
        // Start from the rightmost index and find the first one that can be incremented.
        int i = k - 1;
        while (i >= 0 && indices[i] == i + n - k) {
            i--;
        }

        if (i < 0) {
            // This was the last combination
            this.hasNext = false;
        } else {
            // Increment this index
            indices[i]++;
            // Reset all subsequent indices
            for (int j = i + 1; j < k; j++) {
                indices[j] = indices[j - 1] + 1;
            }
        }
        
        return sb.toString();
    }

    public boolean hasNext() {
        return this.hasNext;
    }
}

Complexity Analysis

Time Complexity: Constructor: `O(K)` to initialize the `indices` array. `next()`: `O(K)`. In the worst case, we scan the entire `indices` array (`O(K)`) to find the pivot, and building the result string also takes `O(K)`. `hasNext()`: `O(1)`.Space Complexity: O(K), where K is the `combinationLength`, to store the `indices` array.

Pros and Cons

Pros:

Extremely memory efficient, using only space proportional to the combination length.
Fast initialization (O(K)), as no heavy computation is done upfront.
Work is distributed across next() calls (lazy evaluation), which is ideal for typical iterator usage patterns.

Cons:

The logic inside the next() method is more complex than in the pre-computation approach.
Each next() call has a slightly higher cost (O(K)) compared to the O(1) of the pre-computation approach.

Code Solutions

Checking out 3 solutions in different languages for Iterator for Combination. Click on different languages to view the code.

class CombinationIterator { private int n ; private int combinationLength ; private String characters ; private StringBuilder t = new StringBuilder (); private List < String > cs = new ArrayList <>(); private int idx = 0 ; public CombinationIterator ( String characters , int combinationLength ) { n = characters . length (); this . combinationLength = combinationLength ; this . characters = characters ; dfs ( 0 ); } public String next () { return cs . get ( idx ++); } public boolean hasNext () { return idx < cs . size (); } private void dfs ( int i ) { if ( t . length () == combinationLength ) { cs . add ( t . toString ()); return ; } if ( i == n ) { return ; } t . append ( characters . charAt ( i )); dfs ( i + 1 ); t . deleteCharAt ( t . length () - 1 ); dfs ( i + 1 ); } } /** * Your CombinationIterator object will be instantiated and called as such: * CombinationIterator obj = new CombinationIterator(characters, combinationLength); * String param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */

Video Solution

Watch the video walkthrough for Iterator for Combination

Patterns:

BacktrackingDesignIterator

Data Structures:

String