Code Implementation

from itertools import combinations

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        self.combos = list(combinations(characters, combinationLength))
        self.index = 0

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

    def hasNext(self) -> bool:
        return self.index < len(self.combos)
      

#include <vector>
#include <string>
#include <algorithm>

class CombinationIterator {
    std::vector<std::string> combos;
    int idx = 0;
public:
    CombinationIterator(std::string characters, int combinationLength) {
        std::string bitmask(combinationLength, 1);
        bitmask.resize(characters.size(), 0);
        do {
            std::string comb;
            for (int i = 0; i < characters.size(); ++i)
                if (bitmask[i]) comb += characters[i];
            combos.push_back(comb);
        } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
    }
    
    std::string next() {
        return combos[idx++];
    }
    
    bool hasNext() {
        return idx < combos.size();
    }
};
      

import java.util.*;

class CombinationIterator {
    List<String> combos;
    int idx;

    public CombinationIterator(String characters, int combinationLength) {
        combos = new ArrayList<>();
        combine(characters, combinationLength, 0, new StringBuilder());
        idx = 0;
    }

    private void combine(String chars, int k, int start, StringBuilder sb) {
        if (k == 0) {
            combos.add(sb.toString());
            return;
        }
        for (int i = start; i < chars.length(); i++) {
            sb.append(chars.charAt(i));
            combine(chars, k - 1, i + 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public String next() {
        return combos.get(idx++);
    }

    public boolean hasNext() {
        return idx < combos.size();
    }
}
      

class CombinationIterator {
    constructor(characters, combinationLength) {
        this.combos = [];
        this.index = 0;
        this._generate(characters, combinationLength, 0, []);
    }
    _generate(chars, k, start, path) {
        if (k === 0) {
            this.combos.push(path.join(''));
            return;
        }
        for (let i = start; i < chars.length; i++) {
            path.push(chars[i]);
            this._generate(chars, k - 1, i + 1, path);
            path.pop();
        }
    }
    next() {
        return this.combos[this.index++];
    }
    hasNext() {
        return this.index < this.combos.length;
    }
}
      

Problem Description

You are given a string characters that contains only distinct lowercase English letters, and an integer combinationLength. Implement a class CombinationIterator that supports the following operations:

• next(): Returns the next combination of length combinationLength in lexicographical order.
• hasNext(): Returns true if and only if there is a next combination.

Each combination must use each character at most once and must be in lexicographical (dictionary) order. The iterator should efficiently generate combinations on demand.

Thought Process

At first glance, the problem asks us to generate all possible combinations of a given length from a set of unique characters, and return them one at a time in order. The brute-force way would be to generate all combinations up front and store them, but that may not be optimal if there are many combinations and only a few are needed.

However, since the combination length is small (as per problem constraints), precomputing all combinations is often acceptable. The real challenge is ensuring that combinations are generated in lexicographical order and that each is unique, using each character only once per combination.

An analogy is like picking teams of a certain size from a lineup, going through all possible ordered selections without repeats.

Solution Approach

To solve this problem, we need to efficiently generate all possible combinations of the given length from the characters, in lexicographical order. Here’s how we can approach this:

• Step 1: Generate All Combinations
  • We can use recursion or built-in functions (like Python's itertools.combinations) to generate all possible combinations of the required length.
  • Each combination is a unique selection of characters, taken in order, with no repeats.
• Step 2: Store Combinations
  • Store the generated combinations in a list or array.
  • This allows us to access combinations by index and move to the next one efficiently.
• Step 3: Implement the Iterator
  • Maintain an index pointer to track the current combination.
  • next() returns the current combination and advances the pointer.
  • hasNext() checks if the pointer is within the bounds of the stored combinations.

This approach is simple and works well within the problem's constraints. For very large inputs, a more memory-efficient (on-the-fly) generator could be used, but for typical constraints, precomputing is the most straightforward.

Example Walkthrough

Suppose characters = "abc" and combinationLength = 2.

• All possible combinations of length 2 are:
  • "ab"
  • "ac"
  • "bc"
• The iterator starts at the first combination:
  • Call next() → returns "ab"
  • Call hasNext() → returns true
  • Call next() → returns "ac"
  • Call hasNext() → returns true
  • Call next() → returns "bc"
  • Call hasNext() → returns false (no more combinations)
• At each step, the iterator simply returns the next combination from the list and advances its pointer.

Time and Space Complexity

• Brute-force Approach:
  • Time to generate all combinations: O(C(n, k)), where n is the number of characters and k is the combination length.
  • Space: O(C(n, k)), since all combinations are stored.
  • Each next() and hasNext() call is O(1), as they only access the stored list.
• Optimized/On-the-fly Approach:
  • Time per next(): O(k), since generating the next combination requires updating up to k indices.
  • Space: O(k), only storing the current combination.
  • However, for most constraints, precomputing is preferred for simplicity.

Summary

The CombinationIterator problem is about generating and iterating through all possible combinations of a given length from a set of unique characters, in lexicographical order. The simplest and most effective solution is to precompute all combinations and store them, allowing for efficient next() and hasNext() operations. This approach leverages recursion or built-in libraries for combination generation and maintains a straightforward pointer for iteration. The solution is elegant due to its simplicity and efficiency for the problem's typical constraints.